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

✏️ 문제

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

✏️ 풀이

문제 분류가 Hash라는 것을 알고 풀어서, 처음부터 딕셔너리를 사용하는 방법으로 접근했다.

phone_book의 모든 원소는 접두어 후보이므로 딕셔너리에 dict[접두어] = True 를 넣는다.

이후 다시 phone_book을 탐색한다.

이 때, 한 전화번호를 "한글자 ~ 길이-1" 만큼 잘라서 해당 값을 인덱스로 가지는 원소가 dict에 있는 지 살펴본다.

만약 있다면 접두어가 존재한다는 뜻이므로 바로 False를 리턴한다. 

dict에 있는지 살펴볼 때 KeyError를 피하기 위해 defaultdict를 사용하였다.

✏️ 코드

from collections import defaultdict
def solution(phone_book):
    dict = defaultdict(bool)
    for num in phone_book:
        num = num.replace(" ", "")
        dict[num] = True
    
    for num in phone_book:
        num = num.replace(" ", "")
        for s in range(1, len(num)):
            if dict[num[0:s]] == True: 
                return False
    return True

처음에는 dict에 넣으면서 검사도 동시에 했는데 테스트케이스 20개 중 3개가 실패했다.

앞쪽 원소의 접두어가 뒷부분에 나오는 예외는 커버하지 못한다는 것을 깨닫고 반복문 2개로 분리했다.

from collections import defaultdict
def solution(phone_book):
    dict = defaultdict(bool)
    phone_book.sort()
    for num in phone_book:
        for s in range(1, len(num)+1):
            if dict[num[0:s]] == True:
                return False
        dict[num] = True
    return True

 

위에서 언급한 예외를 정렬을 통해 커버할 수 있었다. (1234 123 이 있으면 123이 먼저 나오게 될테니까)

그러나 시간이 현저히 오래걸렸다.

✏️ 다른 사람 풀이

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
            
    return True

해쉬를 이용하지 않은 다른 풀이다. zip이라는 함수를 새롭게 알게되었다.