1. 서론
프로그래밍 언어의 성장이 함께하면서, 다양한 자료구조와 알고리즘이 필요하게 되었습니다. 그 중에서 트라이는 문자열을 효율적으로 처리하는데 특화된 자료구조로, 주로 문자열 검색, 자동완성 기능, 접두어 집합 저장 등에 사용됩니다. 이 글에서는 트라이 자료구조를 활용한 알고리즘 문제를 소개하고, C#으로 문제를 풀어보겠습니다.
2. 트라이(Trie) 자료구조의 이해
트라이는 다형적인 속성을 가지며, 노드들은 각 문자를 나타냅니다. 트라이는 다음과 같은 특성을 가지고 있습니다:
- 모든 단어를 저장할 수 있는 능력.
- 단어의 접두어를 쉽게 검색할 수 있는 능력.
- 접두어가 같은 단어를 그룹화할 수 있는 구조.
트라이는 일반적으로 다음과 같은 방식으로 구성됩니다:
class TrieNode {
Dictionary Children;
bool IsEndOfWord;
public TrieNode() {
Children = new Dictionary();
IsEndOfWord = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void Insert(string word) {
TrieNode current = root;
foreach (char c in word) {
if (!current.Children.ContainsKey(c)) {
current.Children[c] = new TrieNode();
}
current = current.Children[c];
}
current.IsEndOfWord = true;
}
public bool Search(string word) {
TrieNode current = root;
foreach (char c in word) {
if (!current.Children.ContainsKey(c)) {
return false;
}
current = current.Children[c];
}
return current.IsEndOfWord;
}
public bool StartsWith(string prefix) {
TrieNode current = root;
foreach (char c in prefix) {
if (!current.Children.ContainsKey(c)) {
return false;
}
current = current.Children[c];
}
return true;
}
}
3. 문제 소개
이번 강좌에서 다룰 문제는 다음과 같습니다:
문제: 특정 접두사를 가진 단어의 개수 구하기
주어진 단어 목록과 특정 접두사 prefix가 있을 때, 이 접두사로 시작하는 단어의 개수를 반환하는 함수를 작성하세요.
입력:
- 단어 목록: [“apple”, “app”, “application”, “apricot”]
- 접두사: “app”
출력: 3 (단어 목록에서 “app”, “apple”, “application”이 있다.)
4. 문제 해결 과정
문제를 해결하기 위해 트라이 자료구조를 사용하여 단어를 삽입하고, 특정 접두사로 시작하는 단어의 개수를 세는 함수를 구현할 것입니다.
1. **단어 삽입**: 먼저 모든 단어를 트라이에 삽입해야 합니다. 이를 통해 각 단어의 문자별로 자식 노드가 생성됩니다.
2. **접두사 검색**: 특정 접두사로 깊이 탐색하면서, 해당 접두사로 시작하는 모든 단어의 개수를 세는 로직을 구현합니다.
3. **결과 반환**: 접두사로 시작하는 단어의 개수를 반환합니다.
4.1 코드 구현
아래는 C#으로 구현한 전체 코드입니다:
class Solution {
public int CountWordsWithPrefix(string[] words, string prefix) {
Trie trie = new Trie();
// 모든 단어를 트라이에 삽입
foreach (string word in words) {
trie.Insert(word);
}
// 접두사로 시작하는 단어의 개수를 세기
return CountWordsStartingWithPrefix(trie, prefix);
}
private int CountWordsStartingWithPrefix(Trie trie, string prefix) {
TrieNode current = trie.Root;
foreach (char c in prefix) {
if (!current.Children.ContainsKey(c)) {
return 0; // 접두사에 해당하는 단어가 없으면 0 반환
}
current = current.Children[c];
}
return CountAllWords(current); // 접두사 아래의 모든 단어 세기
}
private int CountAllWords(TrieNode node) {
int count = 0;
if (node.IsEndOfWord) {
count++; // 현재 노드가 단어의 끝이라면 단어 카운트
}
foreach (var child in node.Children) {
count += CountAllWords(child.Value); // 모든 자식 노드에 대해 재귀 탐색
}
return count;
}
}
5. 시간 복잡도 분석
트라이에 단어를 삽입하는 데 걸리는 시간 복잡도는 O(m)입니다. 여기서 m은 단어의 길이입니다.
접두사를 검색하는 데에는 O(k) (k는 접두사의 길이) 시간이 소요됩니다.
따라서 전체 시간 복잡도는 O(n * m + k), 여기서 n은 단어의 개수입니다.
6. 테스트 케이스
다음은 몇 가지 테스트 케이스입니다:
string[] words = {"apple", "app", "application", "apricot"};
string prefix = "app";
Solution solution = new Solution();
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // 출력: 3
words = new string[] {"banana", "bandana", "band"};
prefix = "ban";
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // 출력: 3
words = new string[] {"car", "cart", "cat"};
prefix = "ca";
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // 출력: 3
words = new string[] {"dog", "deer", "dough"};
prefix = "do";
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // 출력: 3
7. 결론
이번 글에서는 트라이 자료구조를 이용해 문자열 처리 문제를 해결하는 방법에 대해 알아보았습니다. 트라이는 많은 분야에서 다양한 용도로 사용되며, 문자열 검색과 같은 문제를 해결하기에 아주 유용한 데이터 구조입니다. 트라이의 핵심 아이디어와 함께 C#을 통한 구현을 살펴보았으며, 다양한 테스트 케이스를 통하여 문제 해결 능력을 향상시킬 수 있기를 바랍니다.