프로그래머스 level 2 - 전화번호 목록 (해시)

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

• 이중 for문을 사용하여, 인접한 원소끼리, 길이가 짧은 값이 긴 값의 앞부분에 해당하면 False를 반환하도록 하였다. 그러나 두개의 테스트 케이스에서 오답이 나온다.

• 그나저나 string 자료형 끼리도 if ~ in 구문이 먹히더라. 그런 경우 접두사가 아닌 경우에도 True를 반환하기 때문에 사용은 안했다.

  A = "111"
  B = "a111"
  print(A in B)
  # True

def solution(phone_book):
    p = phone_book
    for i in range(len(p)):
        for j in range(i+1, len(p)):
            if len(p[i]) <= len(p[j]):
                n = len(p[i])
                if p[j][0:n] == p[i]:
                    return False
    return True

• 질문하기에서 8, 9번 케이스에서 걸리는 경우 정렬 후 해보라는 말을 보고 정렬 후, 길이를 비교하는 if문을 빼니 정답이 된다.

• 인접한 원소 중에서도 왼쪽 원소가 더 긴 경우도 있어서 그런 것 같다.

• string 자료형이 들어있는 배열을 정렬할 경우, 길이가 더 짧더라도 아스키 값이 빠른 값을 우선으로 정렬한다.

  a = ["22", "111"]
  a.sort()
  print(a)
  # ['111', '22']

그래서 나의 답은

def solution(phone_book):
    p = phone_book
    p.sort()
    for i in range(len(p)):
        for j in range(i+1, len(p)):
            # if len(p[i]) <= len(p[j]):
            n = len(p[i])
            if p[j][0:n] == p[i]:
                return False
    return True

다른 사람 풀이를 보고 해시로 풀어보았다.

• hash의 key 값에 번호들을 넣어둔 다음, for문을 다시 돌려, 번호의 앞에서부터 tmp에 더해가며, 해시에 key값에 이미 있으면서도 같지 않으면 False를 return한다.

• 효율성면에서 더 좋다.

def solution(phone_book):
    h = {}
    for pn in phone_book:
        h[pn] = 1
    for pn in phone_book:
        tmp = ""
        for p in pn:
            tmp += p
            if tmp in h.keys():
                if tmp != pn:
                    return False
    return True