11_trie.cpp

Download
cpp 358 lines 10.4 KB 
  1/*
  2 * 트라이 (Trie)
  3 * Prefix Tree, Autocomplete, Word Search
  4 *
  5 * λ¬Έμžμ—΄ 검색에 νŠΉν™”λœ 트리 μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <string>
 11#include <unordered_map>
 12#include <memory>
 13
 14using namespace std;
 15
 16// =============================================================================
 17// 1. 기본 트라이
 18// =============================================================================
 19
 20class Trie {
 21private:
 22    struct TrieNode {
 23        unordered_map<char, unique_ptr<TrieNode>> children;
 24        bool isEndOfWord = false;
 25    };
 26
 27    unique_ptr<TrieNode> root;
 28
 29public:
 30    Trie() : root(make_unique<TrieNode>()) {}
 31
 32    void insert(const string& word) {
 33        TrieNode* node = root.get();
 34        for (char c : word) {
 35            if (!node->children.count(c)) {
 36                node->children[c] = make_unique<TrieNode>();
 37            }
 38            node = node->children[c].get();
 39        }
 40        node->isEndOfWord = true;
 41    }
 42
 43    bool search(const string& word) const {
 44        const TrieNode* node = root.get();
 45        for (char c : word) {
 46            if (!node->children.count(c)) {
 47                return false;
 48            }
 49            node = node->children.at(c).get();
 50        }
 51        return node->isEndOfWord;
 52    }
 53
 54    bool startsWith(const string& prefix) const {
 55        const TrieNode* node = root.get();
 56        for (char c : prefix) {
 57            if (!node->children.count(c)) {
 58                return false;
 59            }
 60            node = node->children.at(c).get();
 61        }
 62        return true;
 63    }
 64};
 65
 66// =============================================================================
 67// 2. μžλ™μ™„μ„± 트라이
 68// =============================================================================
 69
 70class AutocompleteTrie {
 71private:
 72    struct TrieNode {
 73        unordered_map<char, unique_ptr<TrieNode>> children;
 74        bool isEndOfWord = false;
 75        int frequency = 0;
 76    };
 77
 78    unique_ptr<TrieNode> root;
 79
 80    void collectWords(TrieNode* node, string& current, vector<string>& result) {
 81        if (node->isEndOfWord) {
 82            result.push_back(current);
 83        }
 84        for (auto& [c, child] : node->children) {
 85            current.push_back(c);
 86            collectWords(child.get(), current, result);
 87            current.pop_back();
 88        }
 89    }
 90
 91public:
 92    AutocompleteTrie() : root(make_unique<TrieNode>()) {}
 93
 94    void insert(const string& word, int freq = 1) {
 95        TrieNode* node = root.get();
 96        for (char c : word) {
 97            if (!node->children.count(c)) {
 98                node->children[c] = make_unique<TrieNode>();
 99            }
100            node = node->children[c].get();
101        }
102        node->isEndOfWord = true;
103        node->frequency += freq;
104    }
105
106    vector<string> autocomplete(const string& prefix) {
107        vector<string> result;
108        TrieNode* node = root.get();
109
110        for (char c : prefix) {
111            if (!node->children.count(c)) {
112                return result;
113            }
114            node = node->children[c].get();
115        }
116
117        string current = prefix;
118        collectWords(node, current, result);
119        return result;
120    }
121};
122
123// =============================================================================
124// 3. μ™€μΌλ“œμΉ΄λ“œ 검색 트라이
125// =============================================================================
126
127class WildcardTrie {
128private:
129    struct TrieNode {
130        TrieNode* children[26] = {nullptr};
131        bool isEndOfWord = false;
132        ~TrieNode() {
133            for (auto& child : children) delete child;
134        }
135    };
136
137    TrieNode* root;
138
139    bool searchHelper(TrieNode* node, const string& word, int idx) {
140        if (!node) return false;
141        if (idx == (int)word.size()) return node->isEndOfWord;
142
143        char c = word[idx];
144        if (c == '.') {
145            // μ™€μΌλ“œμΉ΄λ“œ: λͺ¨λ“  μžμ‹ 탐색
146            for (int i = 0; i < 26; i++) {
147                if (searchHelper(node->children[i], word, idx + 1)) {
148                    return true;
149                }
150            }
151            return false;
152        } else {
153            return searchHelper(node->children[c - 'a'], word, idx + 1);
154        }
155    }
156
157public:
158    WildcardTrie() : root(new TrieNode()) {}
159    ~WildcardTrie() { delete root; }
160
161    void addWord(const string& word) {
162        TrieNode* node = root;
163        for (char c : word) {
164            int idx = c - 'a';
165            if (!node->children[idx]) {
166                node->children[idx] = new TrieNode();
167            }
168            node = node->children[idx];
169        }
170        node->isEndOfWord = true;
171    }
172
173    bool search(const string& word) {
174        return searchHelper(root, word, 0);
175    }
176};
177
178// =============================================================================
179// 4. 단어 사전 (Word Break)
180// =============================================================================
181
182class WordDictionary {
183private:
184    struct TrieNode {
185        unordered_map<char, TrieNode*> children;
186        bool isEnd = false;
187    };
188
189    TrieNode* root;
190
191public:
192    WordDictionary() : root(new TrieNode()) {}
193
194    void addWord(const string& word) {
195        TrieNode* node = root;
196        for (char c : word) {
197            if (!node->children.count(c)) {
198                node->children[c] = new TrieNode();
199            }
200            node = node->children[c];
201        }
202        node->isEnd = true;
203    }
204
205    bool wordBreak(const string& s) {
206        int n = s.size();
207        vector<bool> dp(n + 1, false);
208        dp[0] = true;
209
210        for (int i = 1; i <= n; i++) {
211            TrieNode* node = root;
212            for (int j = i - 1; j >= 0 && node; j--) {
213                node = node->children.count(s[j]) ? node->children[s[j]] : nullptr;
214                if (node && node->isEnd && dp[j]) {
215                    dp[i] = true;
216                    break;
217                }
218            }
219        }
220
221        return dp[n];
222    }
223};
224
225// =============================================================================
226// 5. XOR 트라이 (μ΅œλŒ€ XOR μ°ΎκΈ°)
227// =============================================================================
228
229class XORTrie {
230private:
231    struct TrieNode {
232        TrieNode* children[2] = {nullptr, nullptr};
233    };
234
235    TrieNode* root;
236    static const int MAX_BITS = 31;
237
238public:
239    XORTrie() : root(new TrieNode()) {}
240
241    void insert(int num) {
242        TrieNode* node = root;
243        for (int i = MAX_BITS; i >= 0; i--) {
244            int bit = (num >> i) & 1;
245            if (!node->children[bit]) {
246                node->children[bit] = new TrieNode();
247            }
248            node = node->children[bit];
249        }
250    }
251
252    int getMaxXOR(int num) {
253        TrieNode* node = root;
254        int maxXor = 0;
255        for (int i = MAX_BITS; i >= 0; i--) {
256            int bit = (num >> i) & 1;
257            int oppositeBit = 1 - bit;
258
259            if (node->children[oppositeBit]) {
260                maxXor |= (1 << i);
261                node = node->children[oppositeBit];
262            } else if (node->children[bit]) {
263                node = node->children[bit];
264            } else {
265                break;
266            }
267        }
268        return maxXor;
269    }
270};
271
272int findMaximumXOR(const vector<int>& nums) {
273    XORTrie trie;
274    int maxXor = 0;
275
276    for (int num : nums) {
277        trie.insert(num);
278        maxXor = max(maxXor, trie.getMaxXOR(num));
279    }
280
281    return maxXor;
282}
283
284// =============================================================================
285// ν…ŒμŠ€νŠΈ
286// =============================================================================
287
288int main() {
289    cout << "============================================================" << endl;
290    cout << "트라이 예제" << endl;
291    cout << "============================================================" << endl;
292
293    // 1. 기본 트라이
294    cout << "\n[1] 기본 트라이" << endl;
295    Trie trie;
296    trie.insert("apple");
297    trie.insert("app");
298    trie.insert("application");
299    cout << "    μ‚½μž…: apple, app, application" << endl;
300    cout << "    search(\"apple\"): " << (trie.search("apple") ? "있음" : "μ—†μŒ") << endl;
301    cout << "    search(\"app\"): " << (trie.search("app") ? "있음" : "μ—†μŒ") << endl;
302    cout << "    search(\"appl\"): " << (trie.search("appl") ? "있음" : "μ—†μŒ") << endl;
303    cout << "    startsWith(\"app\"): " << (trie.startsWith("app") ? "예" : "μ•„λ‹ˆμ˜€") << endl;
304
305    // 2. μžλ™μ™„μ„±
306    cout << "\n[2] μžλ™μ™„μ„±" << endl;
307    AutocompleteTrie autoTrie;
308    autoTrie.insert("hello");
309    autoTrie.insert("help");
310    autoTrie.insert("helicopter");
311    autoTrie.insert("hero");
312    autoTrie.insert("world");
313
314    cout << "    단어: hello, help, helicopter, hero, world" << endl;
315    auto suggestions = autoTrie.autocomplete("hel");
316    cout << "    \"hel\" μžλ™μ™„μ„±: ";
317    for (const auto& s : suggestions) cout << s << " ";
318    cout << endl;
319
320    // 3. μ™€μΌλ“œμΉ΄λ“œ 검색
321    cout << "\n[3] μ™€μΌλ“œμΉ΄λ“œ 검색" << endl;
322    WildcardTrie wcTrie;
323    wcTrie.addWord("bad");
324    wcTrie.addWord("dad");
325    wcTrie.addWord("mad");
326    cout << "    단어: bad, dad, mad" << endl;
327    cout << "    search(\".ad\"): " << (wcTrie.search(".ad") ? "있음" : "μ—†μŒ") << endl;
328    cout << "    search(\"b..\"): " << (wcTrie.search("b..") ? "있음" : "μ—†μŒ") << endl;
329
330    // 4. 단어 뢄리
331    cout << "\n[4] 단어 뢄리 (Word Break)" << endl;
332    WordDictionary dict;
333    dict.addWord("leet");
334    dict.addWord("code");
335    cout << "    사전: [leet, code]" << endl;
336    cout << "    \"leetcode\" 뢄리 κ°€λŠ₯: " << (dict.wordBreak("leetcode") ? "예" : "μ•„λ‹ˆμ˜€") << endl;
337
338    // 5. μ΅œλŒ€ XOR
339    cout << "\n[5] μ΅œλŒ€ XOR" << endl;
340    vector<int> nums = {3, 10, 5, 25, 2, 8};
341    cout << "    λ°°μ—΄: [3, 10, 5, 25, 2, 8]" << endl;
342    cout << "    μ΅œλŒ€ XOR: " << findMaximumXOR(nums) << endl;
343
344    // 6. λ³΅μž‘λ„ μš”μ•½
345    cout << "\n[6] λ³΅μž‘λ„ μš”μ•½" << endl;
346    cout << "    | μ—°μ‚°        | μ‹œκ°„λ³΅μž‘λ„ | L: λ¬Έμžμ—΄ 길이  |" << endl;
347    cout << "    |-------------|------------|-----------------|" << endl;
348    cout << "    | μ‚½μž…        | O(L)       |                 |" << endl;
349    cout << "    | 검색        | O(L)       |                 |" << endl;
350    cout << "    | 접두사 검색 | O(L)       |                 |" << endl;
351    cout << "    | μžλ™μ™„μ„±    | O(L + K)   | K: κ²°κ³Ό 수      |" << endl;
352    cout << "    | κ³΅κ°„λ³΅μž‘λ„  | O(ALPHABET Γ— L Γ— N) |      |" << endl;
353
354    cout << "\n============================================================" << endl;
355
356    return 0;
357}