코틀린 코딩테스트 강좌, 트라이

1. 트라이(Trie)란?

트라이는 다중 접두사 문자열 검색을 위해 사용하는 트리 자료 구조입니다.
각 노드는 문자열의 각 문자에 대한 경로를 나타내고, 루트부터 리프까지의 경로는 하나의 문자열을
형성합니다. 따라서, 트라이를 사용하면 문자열의 공통 부분을 공유할 수 있어 메모리 효율성이 뛰어납니다.

예를 들어, “cat”, “cab”, “dog”와 같은 단어들이 있을 때, 이 단어들은 트라이를 통해
다음과 같이 저장될 수 있습니다:

                (root)
                ├── c
                │   ├── a
                │   │   ├── b
                │   │   └── t
                │   └── d
                └── d
                    └── o
                        └── g
            

이처럼 트라이는 문자열 집합의 효율적인 저장 및 검색을 위한 강력한 도구입니다.
특히, 접두사 검색, 단어 완성 기능, 사전 순 정렬 문제에 효과적입니다.

2. 트라이 자료구조의 구현

트라이를 구현하기 위해 두 개의 주요 클래스를 정의할 것입니다:
TrieNode와 Trie 클래스입니다.

                class TrieNode {
                    val children: MutableMap = mutableMapOf()
                    var isEndOfWord: Boolean = false
                }
                
                class Trie {
                    private val root: TrieNode = TrieNode()
                    
                    fun insert(word: String) {
                        var node = root
                        for (char in word) {
                            node = node.children.getOrPut(char) { TrieNode() }
                        }
                        node.isEndOfWord = true
                    }
                    
                    fun search(word: String): Boolean {
                        var node = root
                        for (char in word) {
                            node = node.children[char] ?: return false
                        }
                        return node.isEndOfWord
                    }
                }
            

위 코드는 트라이의 기본적인 삽입 및 검색 기능을 제공합니다. TrieNode
클래스는 자식 노드를 저장하고, 단어의 끝을 나타내는 플래그를 담고 있습니다.
Trie 클래스는 삽입과 검색 기능을 제공하며, getOrPut 함수를 사용하여
자식 노드를 동적으로 생성합니다.

3. 문제 설명: 단어 검색

문제: 주어진 단어 리스트와 쿼리 리스트가 있을 때, 각 쿼리가 단어 리스트에 포함되는지
확인하는 프로그램을 작성하시오. 특히, 공통된 접두사를 가지는 단어들을 효율적으로 검색할 수 있도록 합니다.

입력:
– 단어 리스트: [“apple”, “app”, “bat”, “ball”, “batman”]
– 쿼리 리스트: [“app”, “bat”, “banana”, “appl”, “ball”]

출력: 각 쿼리가 단어 리스트에 있는지 여부를
Boolean 값으로 나타내는 리스트를 반환합니다.
예를 들어, [true, true, false, false, true]가 출력되어야 합니다.

4. 문제 해결 과정

위 문제를 해결하기 위해 먼저 단어 리스트를 트라이에 삽입하고,
이후 각 쿼리를 검색하여 결과를 확인하는 방식을 사용할 것입니다.

                fun wordSearch(words: List, queries: List): List {
                    val trie = Trie()
                    for (word in words) {
                        trie.insert(word)
                    }
                    return queries.map { trie.search(it) }
                }
            

wordSearch 함수는 먼저 Trie 객체를 생성하고,
주어진 단어 리스트를 통해 트리에 단어들을 삽입합니다.
이어서 쿼리 리스트를 순회하며 search 메서드를 호출하여
각 쿼리가 존재하는지 여부를 확인합니다.

5. 코드 실행 예제

                fun main() {
                    val words = listOf("apple", "app", "bat", "ball", "batman")
                    val queries = listOf("app", "bat", "banana", "appl", "ball")
                    val result = wordSearch(words, queries)
                    println(result) // [true, true, false, false, true]
                }
            

위의 코드 블록을 실행하면 쿼리에 대한 답을
Boolean 값으로 포함한 리스트가 출력됩니다. 이처럼 트라이는
문자열 검색 문제를 간단하고 효율적으로 해결해줍니다.

6. 트라이의 유용성과 확장

트라이는 문자열 검색 외에도 여러 가지 다른 문제에 응용될 수 있습니다.
예를 들어, 자동 완성 기능, 접두사 검색 기능은 트라이의
가장 일반적인 활용 사례입니다. 또한, 트라이를 통해 문제를
확장하여 추가 기능을 넣을 수도 있습니다. 특정 접두사로 시작하는
모든 단어를 찾는 기능이나 특정 패턴으로 시작하는 단어를 찾는
기능을 구현할 수 있습니다.

예를 들어, 특정 접두사로 시작하는 모든 단어를 찾는
startsWith 메서드를 다음과 같이 추가할 수 있습니다.

                fun startsWith(prefix: String): Boolean {
                    var node = root
                    for (char in prefix) {
                        node = node.children[char] ?: return false
                    }
                    return true
                }
            

이 메서드는 주어진 접두사가 트리에 존재하는지 여부를
확인할 수 있습니다. 이러한 확장 기능은 특히 대용량 데이터
처리 시 매우 유용합니다.

7. 결론

지금까지 코틀린을 사용하여 트라이를 구현하고, 문자열 검색
문제를 해결하는 과정을 살펴보았습니다. 트라이는 문자열을
효율적으로 관리하고 검색하는 데 매우 유용한 자료구조로,
코딩테스트에서의 문제가 많습니다. 문제를 해결하기 위한
다양한 접근 방식을 시도하고, 트라이를 적절히 활용한다면
다양한 알고리즘 문제를 쉽게 해결할 수 있을 것입니다.

다음 강좌에서는 트라이의 변형 및 다른 고급 문자열 알고리즘에 대해
다룰 예정입니다. 더 많은 연습 문제와 실제 코딩테스트 문제를 통해
실력을 쌓아가시기 바랍니다. 감사합니다!