BOJ 5052 전화번호 목록

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

처음에는 Naive하게 문자열을 입력받을 때 마다 지금까지 입력받았던 모든 문자열과 비교하여 일관성을 체크하는 방법을 생각했다.

해당 방법은 시간복잡도 O(t * n ^2) 이니 될리가 없었다.

 

이 문제에서 시간을 줄이기 위해서는 앞서 입력받은 문자열들과 비교하는 횟수를 줄일 필요가 있다.

문자열의 비슷한 구간이 모아져있다면, 비교횟수를 줄일 수 있을 것이라고 생각했고, 이와 비슷한 아이디어로 구현되어있는 trie가 떠올랐다.

그래서 Trie 를 사용하면 될 것 같아 trie를 사용하여 문제를 풀었다.

 

아래 코드는 제출 코드이다.

 

#include <cstdio>

class node{
public:
    node* arr[10];
    bool end;
    void clear(){
        for(int i=0;i<10;i++){
            this->arr[i] = NULL;
        }
        end = false; 
    }
    node(){ this->clear();}
};
node aa[100001];
class trie{
public:
    int idx = 0;
    bool insert(char* a, int n){
        node* now = &(aa[0]);
        node* next;
        for(int i=0;;i++){

            if(a[i]){
                next = now->arr[a[i]-'0'];  
                if(next == 0) {
                    //printf("%d\n", idx);
                    ++idx;
                    now->arr[a[i]-'0'] = &(aa[idx]);
                    now->arr[a[i]-'0']->clear();
                }
                
                now = now->arr[a[i]-'0'];
            }
            else{
                now->end = true;
                for(int i=0;i<10;i++){
                    if(now->arr[i]) return true;
                }
                return false;
            }          
            if(now->end) {
                return true;
            }
        }
    }
    void clear(){
        aa[0].clear();
        idx = 0;
    }
};
trie t;

int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n; scanf("%d",&n);
        char str[11];
        bool flag = false;
        t.clear();

        for(int i=0;i<n;i++){
            scanf("%s",str);
            if(flag) continue;
            //else
            flag = t.insert(str, 0);
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }

    return 0;
}

 

 

PS 1. 문제 풀때 clear 함수에 들어가는 내용을 initializer에 써서 많은 시간을 버린건 아쉬웠다.

PS 2. class 대신 배열로 선언하면 실행시간을 좀 더 줄일 수 있을 것이다.