BOJ)5052 전화번호 목록

문제: icpc.me/5052

전화번호 목록이 주어질 때 전화번호들이 일관성을 띄는지 조사하는 문제이다.

우리는 트라이를 활용하여 전화번호 목록들을 전부 트라이에 insert 한 뒤 

모든 전화번호를 검색하여 문자열이 끝나는 지점에서 아직 더 탐색이 가능한 경우가 존재한다면 일관성이 없다고 결정해주면 된다.

#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;
}