Trie(트라이) 자료구조 정의, 예제 코드

2020 신입 개발자 카카오 블라인드 시험을 치다가,

문자열 처리에 대한 자료구조를 알게 되었다.

 

Trie 자료구조에 대한 다음과 같은 모습으로 생겼다.

 

Trie 자료구조

위에 보면, APPLE, LABLE, CABLE이라는 단어를 넣은 것이다.

왜 굳이, Trie 자료구조를 사용해야 하는지를 생각해보자.

 

특정 문자열을 벡터에서 순차적으로 탐색하면, 최대 문자열의 갯수만큼 걸리게 된다.

하지만 Trie 자료구조를 사용하면, 문자열의 길이만큼의 탐색 시간이 걸린다.

즉, 많은 문자열속에서 특정한 문자열을 찾기 위해서는 Trie만한 자료구조가 없다.

 

Trie 자료 구조를 사용하지 않으면, 카카오 블라인드 2020 기출문제 효율성을 통과할 수 없게끔 설계되어 있다.

Trie 자료 구조를 몰랐을 때 사용했던 방법은,

 

문자열을 일일이 나누어서, Map 자료 구조에 넣었었다. 이 방식으로, 효율성 2번만 시간 초과가 뜨고 나머지는 통과할 수 있었다.

 

 

문자열을 일일이 나눈다는 것이 무슨 말이냐면,

 

Words 자료구조에 apple이 들어있다고 하면,

a????, ap???, app??, appl? 식으로 문자열들을 생성하고 map 자료구조에 넣는 것이다. 

 

 

위에 방식을 시간복잡도 개념으로 접근해보자면,

a를 만들 때, 인덱스 탐색 1회,

ap를 만들 때, 인덱스 탐색 2회,

app를 만들 때, 인덱스 탐색 3회,

appl를 만들 때, 인덱스 탐색 4회,

apple은 굳이 만들 필요가 없어서 생략했다.

 

 

즉, 1 + 2 + 3 + 4 + ... + n - 1 정도 인덱스 탐색이 필요하다.

하지만, Trie 자료구조를 사용하면 문자열 길이만큼의 인덱스 탐색만 필요하다.

 

위에 증명으로, Trie 자료구조가 필요한 이유가 설명되었을 것이다.

 

 

[자료구조 예제 코드]

 
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Trie {
    bool finish;
    Trie* next[26];
    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }
    void insert(const char* key) {
        if ((*key) == '\0') {
            finish = true;
            return;
        };
        int curr = (*key) - 'a';
        if (!next[curr])
            next[curr] = new Trie();
        next[curr]->insert(key + 1);
    }
    bool find(const char* key) {
        if ((*key) == '\0')
            return true;
        int curr = (*key) - 'a';
        if (!next[curr])
            return false;
        return next[curr]->find(key + 1);
    }
};