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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42577

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

먼저 전화번호들에 대해서 count가 1이므로 dictionary를 초기화한다.

그리고 전화번호들에 대해서 앞에서부터 하나씩 접두어를 저장하는 prefix에 저장하고, prefix가 dictionary에 있으면 접두어가 존재하므로 False를 return한다.

시간복잡도는 phone_book의 길이를 n, 전화번호의 길이를 m이라고 하면 O(nm)이다.

def solution(phone_book):
    answer = True
    prefix_dict = {} # key: phone_number, value: phone_number count
    
    
    for phone_number in phone_book:
        prefix_dict[phone_number] = 1
    
    for phone_number in phone_book:
        prefix = ""
        for digit in phone_number:
            prefix += digit
        
            if prefix in prefix_dict and prefix != phone_number:
                return False
                
    return True