프로그래머스 전화번호 목록 파이썬

문제

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

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

풀이

가장 쉬운 방법은 각각의 원소에 대하여 모든 원소와 매칭 하는 것이겠지만, 원소의 개수가 최대 1,000,000개 이므로 O(N^2)의 시간 복잡도로는 시간 초과가 날것이다.

 

따라서 모든 원소를 딕셔너리의 key로 만들어주고 각 원소에 대해서 문자열의 앞부분을 슬라이싱하여 딕셔너리의 key에 존재하는지 확인하였다.

 

딕셔너리에서 key가 존재하는 찾는 시간 복잡도는 O(1)이다.

 

따라서 원소의 개수는 최대 1,000,000개이고 문자열의 길이는 최대 20이므로 19,000,000번 안에 찾을 수 있을 것이다.

코드

def solution(phone_book):
    book = {key: 0 for key in phone_book}
    for num in phone_book:
        for i in range(1, len(num)):
            if num[:i] in book:
                return False
    return True