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

프로그래머스의 레벨 2 문제 전화번호목록

문제 요구 조건

접두어가 리스트에 포함되는지 비교해야한다.

내 풀이 방법

1. 문자열 비교에 걸리는 시간을 단축하기 위해서 해시테이블에 저장하고, 모든 접두어를 만들어서 n*m으로 해결했다.

# 모든 가능한 접두어를 해시테이블에 저장하고 비교하면 n*m. 범위가 작아서 가능

def solution(phone_book):
    d = {phone[:i]: True for phone in phone_book for i in range(1, len(phone))}
    for phone in phone_book:
        if d.get(phone, False):
            return False
    return True

다른 풀이 방법

문자열을 사전식으로 정렬하면 원소의 뒤에 있는 원소에 포함되는지만 비교하면 되므로 N*log N으로 해결할 수 있더라.. 이 생각을 못했다.