[알고리즘 풀이 분석] BOJ 5052 전화번호 목록

오늘 풀어본 문제는 BOJ 5052 전화번호 목록 이다.
예상치 못하게 다음주에 면접이 생겨 준비중인데 자료구조부터 정리하다가 Trie 관련된 추천 문제가 있어 풀어보았다. 사실 트라이를 처음 써보는 것 같은데 개념적으로는 이해가 금방 됐지만 손으로 구현하려면 좀 더 연습이 필요할 것 같다..!

BOJ 5052 전화번호 목록

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

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

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

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

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

입출력

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

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

나의 풀이

이문제를 푸는데 있어 나의 목표는 자료구조 Trie 를 구현해보고 활용 해 보는 것이었다. 이론 공부를 하면서 이애하고 트라이를 구현 해 두었지만 문제 조건에 맞게 바꾸는 과정에서 역시 좀 헷갈렸다.

주어지는 번호들이 모두 서로의 접두어가 되지 않으면 "YES" 를 출력, 하나라도 접두어가 되는 경우가 존재한다면 "NO" 를 출력하는 문제였다.

Trie 에 문자열을 넣으면서 확인해 보려 했는데 너무 헷갈려서 일단 넣고 나중에 확인하는 방식으로 진행하였다.

입력되는 문자열들을 char 배열 char numbers[10001][11] 에 차례대로 넣으면서 Trie 에 삽입해두고 이후에 각 문자열들을 Trie 내에서 검사하면서 해당 문자열이 끝나기 전에 Trie 에 연결된 노드가 끝나면, 즉 해당 문자열의 접두어인 문자열이 존재하면 false 값을 반환하였다.

아직 몇번 더 연습이 필요할 것 같다!

코드

#include <iostream>
#include <vector>

// boj 5052 전화번호 목록, Trie 사용, 골드 4
using namespace std;

struct TRIE {
    bool finish;
    TRIE * Node[26];
    TRIE() {
        finish = false;
        for (int i = 0; i < 26 ; ++i) Node[i] = NULL;
    }

    void insert(char * str){
        if (*str == NULL){
            finish = true;
            return;
        }

        int cur = *str - '0';
        if (Node[cur] == NULL){
            Node[cur] = new TRIE();
        }

        Node[cur]->insert(str+1);
    }

    bool check(char * str) {
        if(*str == NULL) return true;
        if (finish) return false;

        int cur = *str - '0';
        return Node[cur]->check(str+1);
    }
};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin>>T;

    for (int i = 0; i < T; ++i) {
        int N;
        cin>>N;

        char numbers[10001][11];
        TRIE * root = new TRIE();

        for (int j = 0; j < N; ++j) {
            cin>>numbers[j];
            root->insert(numbers[j]);
        }

        bool consistent = true;
        for (int j = 0; j < N; ++j) {
            if (!(root->check(numbers[j]))) {
                consistent = false;
                break;
            }
        }

        if (!consistent) cout<<"NO"<<'\n';
        else cout<<"YES"<<'\n';
    }

    return 0;
}

Reference

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