[Python] 전화번호 목록

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

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

---

 

Point

• 해쉬를 이용한 문제로, 트라이(Trie) 자료구조를 응용해서 풀어보기 좋은 문제이다.
• 실제로 많은 분들이 리스트와 반복문을 이용해서 풀고 있는데, 만약 문제의 제약조건이 타이트했다면 해결하기 어려울 것이다.

Tip

• 정렬을 하지 않는 것이, 최악 테스트케이스에서 수행 시간이 더 빠르다.
• 따라서 prefix+a 문자열이 이미 트라이에 있을 때, prefix의 끝(*)이 prefix+a와 다른지를 판별해준다.
• 같은 관점에서 prefix가 이미 트라이에 있을 때, prefix+a 문자열이 prefix의 끝(*)과 다른지를 판별해준다.  

 

최악 테스트케이스 메모리

242MB

최악 테스트케이스 시간

1064.81ms

결과

정확성: 83.3

효율성: 16.7

합계: 100.0 / 100.0

def solution(phone_book):
    trie = dict()
    for pb in phone_book:
        cur = trie
        for _p in pb:
            keys = list(cur.keys())
            if _p not in keys:
                cur[_p] = dict()
            # 이미 prefix가 있는 상황에서 prefix+a가 들어올 때
            if cur[_p] and '*' in cur[_p].keys():
                return False
            cur = cur[_p]
        # 이미 prefix+a가 있는 상황에서 prefix가 들어올 때
        keys = list(cur.keys())
        if keys and keys[0] != "*":
            return False  
        cur['*'] = True
    return True

 

문제를 푸는데 도움이 된 테스트 케이스