코딩 테스트 대비! 파이썬으로 트라이(Trie) 자료구조 구현하기

파이썬으로 트라이(Trie) 자료구조 구현하기


문제 설명

문자열 배열 `words`와 단일 문자 `char`가 주어졌을 때, `char`를 최소 횟수로 추가하여 `words`의 모든 문자열을 완전히 포함할 수 있는 가장 짧은 문자열을 찾는 함수를 작성하세요.


예시 입출력

입력: words = ["cat", "cats", "catshey", "dog"], char = 's'
출력: "cats"

입력: words = ["hello", "hell", "hello"], char = 'l'
출력: "hello"

솔루션 코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.word = None

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_word = True
        node.word = word

def shortest_word(words, char):
    trie = Trie()
    for word in words:
        trie.insert(word)

    return trie_search(trie.root, char)

def trie_search(node, char):
    if node is None:
        return ""

    if node.is_word:
        word = node.word
    else:
        word = ""

    if char not in node.children:
        return word

    child_word = trie_search(node.children[char], char)
    return child_word + char + word

# 테스트 케이스
print("최단 문자열:", shortest_word(["cat", "cats", "catshey", "dog"], 's'))
print("최단 문자열:", shortest_word(["hello", "hell", "hello"], 'l'))

코드 설명

이 포스팅에서는 트라이(Trie) 자료구조를 활용하여 주어진 문자열 배열에서 가장 짧은 문자열을 찾는 문제를 해결했습니다. 트라이는 문자열 검색 및 조작에 효율적인 트리 기반 자료구조로, 코딩 테스트와 실무에서 다양하게 활용되므로 반드시 학습해야 합니다.

트라이(Trie, 접두사 트리)는 문자열을 효율적으로 저장하고 검색할 수 있는 트리 기반 자료구조입니다. 루트 노드에서 시작하여 각 문자에 해당하는 자식 노드로 이동하며, 문자열의 끝에 도달하면 해당 노드를 플래그로 표시합니다. 이를 통해 문자열의 삽입, 검색, 삭제 등의 연산을 효율적으로 수행할 수 있습니다.

코드에서는 `TrieNode`와 `Trie` 클래스를 정의하여 트라이 자료구조를 구현했습니다. `TrieNode`는 각 노드를 나타내며, `children` 딕셔너리를 사용하여 자식 노드를 저장합니다. `is_word` 플래그는 해당 노드가 문자열의 끝인지 여부를 나타내고, `word` 속성에는 실제 문자열이 저장됩니다.

`Trie` 클래스에서는 `insert` 메소드를 통해 문자열을 삽입할 수 있습니다. `shortest_word` 함수에서는 주어진 `words`를 트라이에 삽입한 후, `trie_search` 함수를 호출하여 가장 짧은 문자열을 찾습니다. `trie_search` 함수는 재귀적으로 트라이를 탐색하며, 각 노드에서 `char`를 추가하여 문자열을 만듭니다.

트라이 자료구조는 다음과 같은 장점이 있어 매우 유용합니다.

1. 검색 효율성 : 문자열의 길이에 관계없이 일정한 시간 복잡도(O(k), k는 문자열 길이)로 검색할 수 있습니다.
2. 공간 효율성 : 중복되는 접두사를 공유하여 메모리 사용량을 절약할 수 있습니다.
3. 다양한 응용 가능 : 문자열 검색, 자동 완성, IP 라우팅 테이블 등 다양한 분야에 활용될 수 있습니다.

이러한 장점 때문에 트라이 자료구조는 문자열 관련 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. 또한 코딩 테스트에서도 자주 출제되므로 반드시 숙지해야 할 자료구조입니다.

트라이 자료구조는 처음에는 어렵게 느껴질 수 있지만, 연습을 통해 익숙해지면 복잡한 문제도 효과적으로 해결할 수 있습니다. 따라서 이 자료구조를 꾸준히 학습하고 연습하는 것이 중요합니다.