[프로그래머스] 전화번호 목록 (level2, python)

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

 

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

---

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

---

입출력 예제

---

입출력 예 설명

 

입출력 예 #1
앞에서 설명한 예와 같습니다.

 

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

 

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

풀이 코드

def solution(phone_book):
    phone_book.sort(key=len)
    hash_table = {}
    min_len = len(phone_book[0])
    
    for p in phone_book:
        for i in range(min_len, len(p)):
            temp = p[:i]
            if temp in hash_table:
                return False
        hash_table[p] = True
                
    return True

사실 해시를 사용하면 겨우 통과되고, 원래는 Trie 알고리즘을 사용해야 하는 것으로 알고 있다.

일단, 전화번호부를 길이를 기준으로 정렬을 한다.

새로이 들어온 전화번호의 접두사를 확인하기 위해 슬라이싱을 할 것인데, 가장 짧은 전화번호부터 비교하면 되기 때문에 min_len이라는 변수로 저장해둔다.

 

일단 N이 100만이고, 내부의 for문은 최대 20회 반복된다.

따라서 2중 for문 내의 로직이 복잡하면 시간복잡도가 터질 수 밖에 없다.

해시인 딕셔너리를 사용하면, in 연산이 O(1)이므로, 시간복잡도를 많이 절감할 수 있다.

 

+ phone_book.sort()로 하면, 테스트 케이스 2개를 통과하지 못한다. 사실 key=len으로 하나 그냥 sort를 하나 별 차이가 없을 것 같았는데, 차이가 생기는 것은 아직 이해하지 못 했다 ㅠㅠ