문제 출처

풀이

해당 문제는 다양하게 풀이가 가능하지만 해시 목록에 있던만큼 해시를 사용해서 문제를 풀고 싶었다.
그래서 생각한 방식은 각 전화번호에서 앞에서 n씩 짤라 확인하는 방법이다.

간단하게 생각한 순서는 아래와 같고, 간단히 구현한 코드도 아래에 있다.
1. 전화번호를 앞에서 n 만큼 분리 후 기존 해시랑 비교
2. 전화번호를 다 분리해서 확인했는데 없으면 해시에 추가, 있으면 종료

def solution(phone_book):
    book = set()
    max_len = 0
    for i in phone_book:
        for j in range(1, len(i)+1):
            if i[:j] in book:
                return False
        book.add(i)
    return True

하지만 이 방식은 정확성 테스트에서 3개의 케이스를 만족하지 못했다.

왜 그런가 확인해보니 정렬를 안하고 검사를해서 주로 짧은 접두사가 뒤에 존재하게 되면 검사가 되지않는다.
접두사가 되기 위해서는 짧아야하며, 짧은 번호가 빨리 해시에 들어가야 했다.

그래서 맨처음에 정렬를 넣었다.

def solution(phone_book):
    book = set()
    max_len = 0
    
    phone_book.sort()
    
    for i in phone_book:
        for j in range(1, len(i)+1):
            if i[:j] in book:
                return False
        book.add(i)
    return True

정렬를 하고 원래대로 진행하니 100점이 나오는걸 볼 수 있었다.