트라이 : Trie

트라이 : Trie

사용 언어: C++

트라이란?

트라이(Trie)는 문자열을 효율적으로 저장하고 탐색하기 위한 트리 기반 자료구조다.

특히 문자열 집합에서 접두어(prefix) 관계를 다루는 문제에 적합하다.

 

예를 들어 "119", "97674233", "1195524421" 같은 전화번호가 있을 때,

트라이는 각 번호를 글자 단위로 쪼개어 루트에서 차례대로 연결하는 방식으로 저장한다.

root
 └── '1'
      └── '1'
           └── '9' (끝 표시, isEnd = true)
                └── '5'
                     └── '5' ...

이 구조 덕분에 특정 문자열이 다른 문자열의 접두어인지 빠르게 판별할 수 있다.

---

기본 구조 (node)

트라이는 각 노드에

1. 자식 노드 집합(children)

2. 문자열이 끝나는 위치인지 여부(isEnd)

를 저장한다.

 

위 전화번호를 저장한다고 가정하면 C++에서는 트라이의 노드를 아래처럼 짤 수 있다.

#include <unordered_map>
#include <string>

struct TrieNode{
    std::unordered_map<char, TrieNode*> children;
    bool isEnd;
    
    TrieNode() : isEnd(false) {}
}

---

삽입 연산 (insert)

문자열을 한 글자씩 순회하며 자식 노드가 없으면 새로 만든다.

마지막 글자에서 isEnd = true;로 표시한다.

void insert(TrieNode* root, const std::string& word)
{
    TrieNode* node = root;
    
    for(char c : word)
    {
    	// 현재 노드의 자식 중 해당 문자가 없으면 새 노드를 생성
    	if(node->children.find(c) == node->children.end())
        {
        	node->children[c] = new TrieNode();
        }
        
        // 자식 노드로 이동
        node = node->children[c];
    }
    
    // 마지막 노드를 단어의 끝으로 표시
    node->isEnd = true;
}

---

탐색 연산 (search)

문자열을 끝까지 따라갈 수 있고, 마지막 노드가 isEnd = true라면 해당 문자열이 존재.

bool search(TrieNode* root, const std::string& word)
{
    TrieNode* node = root;
    
    for(char c : word)
    {
    	// 해시맵에서 key를 검색, 없으면 false
        if(node->children.find() == node->children.end())
        {
        	return false;
        }
        // 존재하면 자식 노드로 이동
     	node = node->children[c];
    }
    
    // 마지막 글자까지 도달 -> isEnd가 true이면 Trie에 정확히 존재
    return node->isEnd;
}

---

전체 코드 : 전화번호 문제 해결 예시

프로그래머스 : 전화번호 목록

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode
{
    unordered_map<char, TrieNode*> children;
    bool bIsEnd;
    
    TrieNode() : bIsEnd(false) {}
};

class Trie {
private:
    TrieNode* root;
    
    void clear(TrieNode* node)
    {
        for(auto& kv : node->children)
        {
            clear(kv.second);
            delete kv.second;
        }
    }

public:
    Trie() { root = new TrieNode(); }
    ~Trie() { clear(root); }
    
    void insert(TrieNode* root, const string& word)
    {
        TrieNode* node = root;
        for(char c : word)
        {
        	// 존재 X
            if(node->children.find(c) == node->children.end())
            {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->bIsEnd = true;
    }
    
    bool search(TrieNode* root, const string& word)
    {
        TrieNode* node = root;
        for(char c : word)
        {
            if(node->children.find(c) == node->children.end())
            {
                return false;
            }
            node = node->children[c];
        }
        return node->bIsEnd;
    }
};

bool solution(vector<string> phone_book) {
    Trie trie;
    for (auto& s : phone_book) {
        if (!trie.insert(s)) return false;
    }
    return true;
}