트라이(Trie) 자료구조

문자열에서 검색을 빠르게 해주는 자료구조 입니다. 정수형 자료형에 대해서 이진검색트리를 이용하면 O(longN)의 시간만에 원하는 데이터를 검색할 수 있습니다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 M이라면 O(MlongN)의 시간 복잡도를 가지게 될 것 입니다. 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 아래그 기름은 문자열 집합 = {"AE", "ATV", "ATES", "ATEV", "DE", "DC"} 가 존재할 때 트라이의 예입니다.

쿼리에 따라서 처리해줄 수 있는 역할이 달라지겠지만 우리는 대부분 문자열이 끝나는 지점을 표시하는 것이 쿼리를 처리할 때 편합니다. 종료 노드를 표시해주면 아래와 같은 그림이 됩니다. 우리는 트리형태를 띄는 트라이에서 검색을 할 경우 최대 트리의 높이까지 탐색하게 됩니다. 따라서 시간복잡도는 O(H)가 됩니다. 하지만 트리의 높이는 최대 문자열의 길이가 되기 때문에 O(M)의 시간복잡도에 문자열 검색이 가능한 것입니다.

백준 관련 문제 : https://www.acmicpc.net/problem/5052 입력받은 숫자열이 일관성이 있는지 없는지를 판단하는 문제입니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 10000
using namespace std;
struct Trie{
    Trie* next[10];
    bool term;
    Trie() : term(false){
        memset(next,0,sizeof(next));
    }
    ~Trie(){
        for(int i=0;i<10;i++){
            if(next[i])
                delete next[i];
        }
    }
    void insert(const char* key){
        if(*key=='\0')
            term=true;
        else{
            int curr = *key-'0';
            if(next[curr]==NULL)
                next[curr]=new Trie();
            next[curr]->insert(key+1);
        }
    }
    bool find(const char* key){
         if(*key=='\0')
            return 0;
        if(term)
            return 1;
        int curr = *key-'0';
        return next[curr]->find(key+1);
    }
};
int t,n,r;
char a[MAX_N][11];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        getchar();
        for(int i=0;i<n;i++)
            scanf("%s",&a[i]);
        Trie *root=new Trie;
        r=0;
        for(int i=0;i<n;i++)
            root->insert(a[i]);
        for(int i=0;i<n;i++){
            if(root->find(a[i])){
                r=1;
            }
        }
        printf("%s\n",r?"NO":"YES");
    }
    return 0;
}