[백준] 5052 전화번호 목록

이 문제는 트라이를 이용하면 풀 수 있다

여태까지 항상 동적 트라이만 짜봤는데 오늘 정적 트라이을 배워서 사용해봤다

 

먼저 문자열배열 s와 trie배열 그리고 문자열의 끝남을 알리는 fin을 잡자

trie가 [10000*10][10] 크기인 이유는 총 10000*10개의 정점이 나올 수 있고

각 정점은 0~9까지 10개의 숫자를 가질 수 있기 때문이다!

 

총 2가지의함수 insert, find를 구현했다!

 

insert에서는 문자열을 trie자료구조에 넣는다

이 때 문자열의 문자 하나씩을 보며 끝난다면 fin[현재정점]을 true로 만들어준다

그럼 우리는 현재정점은 끝나는 지점이라는 것을 알 수 있다

trie배열에는 trie[현재정점][현재문자] = cnt로 인덱스를 매긴다

그럼 문자열을 하나하나 찾을때 정점을 타고들어가서 다음 문자로 갈 수 있고 

fin 배열을 이용해 끝나는지도 확인 할 수 있다

만약 현재 trie[idx][curr]에 값이 있다면 바꾸지 말고 그대로 넘어간다~!

그래야 미리 만들어둔 문자열의 길을 망가뜨리지않고 계속 이어나갈 수 있다!

 

find에서는 문자열을 훑어보며 중간에 끝나는 지점이 있는지 보면 된다

단순하게 fin[idx]가 true 라면 ans=true로 바꿔주고 함수를 끝내자

아니라면 현재 숫자를 curr에 넣고 idx = trid[idx][curr]로 다음 문자로 넘어간다!

이렇게 하나하나 찾아가면서 보면 정적트라이로 답을 찾을 수 있다!

 

소스코드

#include <iostream>
using namespace std;
 
const int N = 10010, M = 11;
int t, n,cnt=1;
 
char s[N][M];
int trie[N * M][M];
bool fin[N * M],ans;
 
void insert(int idx, int pos) {
    for (int i = 0; i < M; i++) {
        if (s[pos][i] == '\0') {
            fin[idx] = true; return;
        }
        int curr = s[pos][i] - '0';
        if (!trie[idx][curr]) trie[idx][curr] = cnt++;
        idx = trie[idx][curr];
    }
}
 
void find(int idx, int pos) {
    for (int i = 0; i < M; i++) {
        if (s[pos][i] == '\0') return;
        if (fin[idx]) {
            ans = true; return;
        }
        int curr = s[pos][i] - '0';
        idx = trie[idx][curr];
    }
}
 
int main() {
    scanf(" %d", &t);
    while (t--) {
        for (int i = 0; i <= cnt; i++) {
            fin[i] = false;
            for (int j = 0; j < 11; j++) trie[i][j] = 0;
        }
        cnt = 1;
        scanf(" %d", &n);
        for (int i = 0; i < n; i++) {
            scanf(" %s", &s[i]);
            insert(0, i);
        }
        ans = false;
        for (int i = 0; i < n; i++) find(0, i);
        if (ans) puts("NO");
        else puts("YES");
    }
}