[프로그래머스 42577 파이썬] 전화번호 목록 (level 2, 해시)

알고리즘 유형 : 해시
풀이 참고 없이 스스로 풀었나요? : X

https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3

소스 코드(파이썬)

def solution(phone_book):
    answer = True
    
    phone_dict = {}
    for key in phone_book:
        phone_dict[key] = 1
    
    for phone_num in phone_dict:
        tmp = ''
        for num in phone_num:
            tmp += num
            if tmp in phone_dict and tmp != phone_num:
                answer = False
                return answer
    
    return answer

풀이 요약

1. 핵심 로직

   phone_book을 딕셔너리로 변환해준다.

   딕셔너리의 모든 키를 for로 순회하면서, 각 키마다 어떤 로직을 실행해준다.

   키의(번호) 맨 왼쪽 문자부터 차례대로 하나 씩 늘려가면서(tmp), 각 단계에서 그 것이 딕셔너리의 keys에 존재하는지 판별한다. 만약 존재한다면 해당 키의 접두사가 존재한다는 뜻이므로 False를 리턴한다.

2. 딕셔너리에서 keys에서 특정 key를 찾는 것은 O(1)이기 때문에 배열을 그대로 사용한 풀이보다 시간복잡도 측면에서 효율적이다.

배운 점, 어려웠던 점

• 딕셔너리는 해시 테이블 개념을 사용하여, 키 값을 찾을 때 O(1)이 걸린다는 것을 알게 되었다.

• 접두사를 찾는 알고리즘을 생각해내지 못했다.