프로그래머스 - 전화번호 목록 (python)

문제

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

아이디어 1

1. N = 1,000,000 이므로 O(N)으로 문제를 풀어야겠다.
   -> str 원소를 기준으로 sort해서 시작 번호가 똑같은 전화번호가 인접하도록 함
   -> 한 번호가 다른 번호의 접두어면 False 리턴

코드 1

def solution2(p):
    p.sort()
    print(p)
    for i, j in zip(p,p[1:]):
        li = len(i)
        if j[:li] == i:
            return False
    return True

아이디어 2

2. hash 문제이므로 dictionary를 사용.
   -> 전화번호의 길이를 기준으로 sort하여 짧은 번호가 앞으로 오게 함
   -> 해당 번호를 숫자 하나씩 나누어 tmp에 저장하고 tmp가 dictionary에 있으면 False반환, 없으면 해당 번호 dictionary에 저장

코드 2

def solution(pb):
    d = dict()
    pb.sort(key = lambda x: len(x))
    
    for p in pb:
        tmp = ''
        for i in range(len(p)):
            tmp += p[i]
            if tmp in d:
                return False
        d[p] = 1
    return True