BOJ 5052 Phone List ( 전화번호 목록 )

 

문제 링크 : https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

트라이(trie) 기본 문제.

아호-코라식(Aho-Corasick) 알고리즘을 복습하기 전에 다시 풀어 봤다.

 

입력받은 문자열을 저장할 strs를 동적으로 할당하면 메모리는 많이 절약되지만 시간은 살짝 더 걸린다.

 

#include<bits/stdc++.h>

using namespace std;

vector<char*> strs;

struct trie {
    char c; bool isEnd;
    trie* children[10];
    trie() : isEnd{false} {
        for(int i=0;i<10;i++) children[i]=nullptr;
    }
    ~trie() {
        for(int i=0;i<10;i++) if(children[i]!=nullptr)
            delete children[i];            
    }
    
    void add(char *p){
        if(*p==0) { isEnd=true; return;}
        
        int id=*p-'0';
        if(children[id]==nullptr)
            children[id]=new trie();
        children[id]->add(p+1);
    }
    
    bool recog(char *p){
        if(*p==0) return true;
        
        if(isEnd) return false;
        int id=*p-'0';
        return children[id]->recog(p+1);
    }
} *rt;

void solve(){
    int n; scanf("%d",&n);
    strs=vector<char*>(n,nullptr);
    for(int i=0;i<n;i++) {
        strs[i]=new char[11];
        scanf("%s", strs[i]);
    }
    
    rt=new trie();
    for(int i=0;i<n;i++) rt->add(strs[i]);
    
    bool ans=true;
    for(int i=0;i<n;i++) 
        if(rt->recog(strs[i])==false) {
            ans=false; 
            break;
        }
    
    if(!ans) printf("NO\n");
    else printf("YES\n");
    
    delete rt, rt=nullptr; 
    for(int i=0;i<n;i++) delete[] strs[i];
}

int main(){
    int T; scanf("%d",&T);
    while(T--)
        solve();
}