[프로그래머스-42577] 전화번호목록 #해시(Hash) #트라이(Trie) #세트(Set)

1. 프로그래머스-(42577 전화번호 목록)

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

프로그래머스

2. 알고리즘 카테고리 : 해시

---

3. 나의 풀이 알고리즘(1차) : 트라이

class TrieNode:
    def __init__(self):
        self.word = False
        self.children = {}
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.word = False
        node.word = True
    
    # 단어가 전부 존재하는지 여부
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return True
            node = node.children[char]
        return node.word
    '''
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False 
            node = node.children[char]
        return True
    '''
    
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return True 
            node = node.children[char]
        if node.word == True:
            return True
        else:
            return False   

def solution(phoneBook):
    phoneBook = sorted(phoneBook, key=len)
    answer = True
    t = Trie()
    length = len(phoneBook)
    
    for phone in phoneBook:
        t.insert(phone)
        
    for phone in phoneBook:
        if not t.startsWith(phone):
            return False
    return answer

-> 트라이로 풀었더니, 정확성은 통과이나... 효율성에서 통과가 안되었다. 찾아보니 프로그래머스 테스트케이스가 2021년 바뀌었는데 그 이전에는 트라이 풀이로 푼 사람도 있었으나 지금은 효율성 문제가 걸리는 것 같다... 테스트 케이스를 아주 잘 바꿔주셨구나... 백준에도 같은 문제가 있는데 트라이로 풀리는 것 같다. 

-> 추가적으로 C++로 풀어보니 트라이도 효율성 합격으로 나오는걸 보아 파이썬에서 class 객체 접근 시 시간이 오래 걸리는 문제가 딱 이거에 해당하는 것 같다. 

 

[트라이 시간복잡도]

- 해당 문제에서 제시한 문자열의 최대 길이 = 20자, 문자열의 총 수 = 1,000,000개 이다.

• 생성 시간 복잡도 : O(M * L = 20 * 10^6 ) 
• 탐색 시간 복잡도 : O(L = 20)

- 따라서 시간복잡도는 이론상 타임아웃이 날 수가 없는데 타임아웃이 나버렸다...

- 트라이 자료구조 및 시간복잡도는 아래 블로그 글을 참고하였다.

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie

[자료구조] 트라이 (Trie)

---

3. 나의 풀이 알고리즘(2차) : 해시

- 처음에 해시 풀이방법이 생각이 안나서 트라이를 사용했지만 해시 카테고리로 분류된 문제였기 때문에 어떻게든 해시로 풀어보고자 하였다.

from collections import defaultdict

def solution(phoneBook):
    hash = {}
    
    for phone in phoneBook:
        hash.setdefault(phone, 1)
    
    for phone in phoneBook:
        temp = ""
        for p in phone:
            temp += p
            if temp in hash and temp != phone:
                return False
    return True

-> 아래 프로세스를 통해서 해시맵에서 접두사와 일치하는 key가 있는지 확인해 주었다.

- 이렇게 했더니 효율성까지 통과 완료!!