5052 전화번호 목록

TRIE 문제.

입력되는 전화번호를 TREE형태로 저장한다.

한 TRIE 경로가 다른 TRIE 경로에 완전히 포함되는 경우 일관성이 없다고 한다.

이걸 찾기 위해서 TRIE구조 안에 bool값 두개 넣는다.

ce = child exist

ee = end exist

대충 이런의미로 넣었다.

TRIE에 전화번호 a를 삽입하는 도중에 ee == 1, 즉 그 부분을 마지막으로 하는 전화번호 b가 존재한다면 일관성이 없다.

또한 a를 삽입할 때 마지막 부분에서 ce == 1, 즉 a를 포함하는 전화번호 b가 존재한다면 일관성이 없다.

#include <stdio.h>
 
bool flag;
 
struct TRIE {
    TRIE* c[10];
    // child exist, ended
    bool ce, ee;
    TRIE() {
        for (int i = 0; i < 10; i++) c[i] = nullptr;
        ce = ee = false;
    }
    ~TRIE() {
        for (int i = 0; i < 10; i++) 
            delete c[i];
    }
    void insert(char* key) {
        if (*key == 0) {
            ee = true;
            if (ce) flag = 1;
        }
        else if (ee) 
            flag = 1;
        else {
            int next = key[0] - '0';
            ce = 1;
            if (!c[next])
                c[next] = new TRIE;
            c[next]->insert(key + 1);
        }
    }
};
 
int t, n;
 
int main() {
    //freopen("Text.txt", "r", stdin);
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        flag = false;
        TRIE* r = new TRIE;
        char s[12];
        for (int i = 0; i < n; i++) {
            scanf("%s", &s);
            // TRIE
            if (!flag) r->insert(s);
        }
        printf(flag ? "NO\n" : "YES\n");
        delete r;
    }
    return 0;
}