[Python] 프로그래머스 / 전화번호 목록 - 뻘짓한 풀이와 완전 짧은 풀이

문제링크

 

Trie 자료구조란

 

Trie(트라이)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 기반 자료구조이다. 일반적으로 문자열이나 단어의 집합을 처리하는 데 유용하다. 주로 자동완성, 사전 등과 같은 목적으로 해당 자료구조를 사용한다.

 

가장 기초적인 코드는 다음과 같다:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def delete(self, word):
        self._delete(self.root, word, 0)

    def _delete(self, node, word, depth):
        if depth == len(word):
            if not node.is_end_of_word:
                return False
            node.is_end_of_word = False
            return len(node.children) == 0
        char = word[depth]
        if char not in node.children:
            return False
        should_delete_child = self._delete(node.children[char], word, depth + 1)
        if should_delete_child:
            del node.children[char]
            return len(node.children) == 0
        return False

 

내 풀이

 

이 문제는 단어가 아닌 전화번호에 대한 문제이지만, 내 풀이는 바로 이 Trie 자료구조를 이용한 것이었는데, 이유는 전화번호부에 최대 100만개의 전화번호가 있다는 문제조건 때문이었다. 프로그래머스에서 10초 내에 문제를 풀고 싶다면 총 시간복잡도 계산한 결과가 1억을 넘어가는 것은 지양해야 하기 때문에, 나는 Trie 자료구조를 선택했던 것인데, 결과부터 말하면 잘못된 선택이었다.

 

그리고 사실 무엇보다도, 실전 코테에서 class를 짜고 앉아있을 시간은 없으므로 이런 풀이는 올바른 풀이가 아니다.
 

class Node:
    def __init__(self):
        self.children = dict()
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, number):
        node = self.root
        for digit in number:
            if digit not in node.children:
                node.children[digit] = Node()
            node = node.children[digit]
            if node.is_end:  
                return False
        node.is_end = True
        return True

    def is_prefix(self, number):
        node = self.root
        for digit in number:
            if digit not in node.children:
                return False
            node = node.children[digit]
            if node.is_end:
                return True
        return False

def solution(phone_book):
    trie = Trie()

    for number in phone_book:
        if not trie.insert(number): 
            return False

    for number in phone_book:
        if trie.is_prefix(number[:-1]):  
            return False

    return True

 

훨씬 짧은 코드

 

저렇게 무식한 풀이 말고, 진짜 훨씬 짧은 풀이도 가능하다. 해쉬구조를 이용한 풀이이다.

def solution(phone_book):
    phone_book_dict = dict()
    
    for number in phone_book:
        phone_book_dict[number] = 1
    
    for number in phone_book:
        for i in range(len(number)):
            if number[:i] in phone_book_dict.keys():
                return False
    
    return True