[C++] 백준 5052번 : 전화번호 목록

문제

 

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

 

입력

 

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

출력

 

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

 

풀이

 

#include <iostream>
using namespace std;
 
bool consistency;
 
class TRIE {
public:
    TRIE* child[10]; // A - Z
    bool is_terminal;
    TRIE() {
        is_terminal = false;
        for (int i = 0; i < 10; ++i) child[i] = nullptr;
    }
 
    ~TRIE() {
        for (int i = 0; i < 26; ++i) {
            if (child[i] != nullptr)
                delete(child[i]);
        }
    }
 
    void insert(const char *key) {
        TRIE *ptr = this;
        for (int i = 0; key[i]; ++i) {
            if (ptr->child[key[i] - '0'] == nullptr) {
                ptr->child[key[i] - '0'] = new TRIE;
            }
            if (ptr->child[key[i]-'0']->is_terminal) consistency = false;
            ptr = ptr->child[key[i] - '0'];
        }
        for(int i = 0 ; i < 10 ; i++){
            if(ptr->child[i]!= nullptr) consistency = false;
        }
        ptr->is_terminal = true;
    }
};
 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        TRIE* trie = new TRIE;
        consistency = true;
        int n;
        scanf("%d",&n);
        while(n--){
            char tmp[15];
            scanf("%s",tmp);
            if(consistency) trie->insert(tmp);
        }
        if(consistency) printf("YES\n");
        else printf("NO\n");
    }
}

트라이 문제!

정렬 사용하면 트라이 안 써도 풀 수 있다고 하지만 트라이 연습을 위해 트라이로 풀어보았다

전화번호가 들어오면 trie에 insert를 한다!

이때 이미 일관성이 깨진 상황이면 속도 향상을 위해 insert를 하지 않고 문자열 입력만 받아보았다

 

일관성을 확인하기 위해 insert 함수 내에서 consistency라는 변수를 활용해주었다

전화번호를 insert 하는 와중에 현재 insert하는 전화번호가 끝나지 않은 상황에서 이미 끝난 전화번호가 있다면

consistency를 false로 바꾸어준다

또한 insert가 끝났을 때 insert 한 문자열을 포함하는 문자열이 있는지 확인하여 있다면 consistency를 false로 바꾸어준다

 

마지막으로 consistency에 따라 다른 출력을 나타낸다