본문 바로가기

알고리즘 관련/BOJ

BOJ)5052 전화번호 목록

문제: icpc.me/5052


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ) 10282 Failing Components  (0) 2017.02.04
BOJ)9202 Boggle  (0) 2017.02.04
BOJ)2662 기업투자  (0) 2017.02.03
BOJ)9252 LCS 2  (0) 2017.02.02
BOJ)1701 Cubeditor  (0) 2017.02.01