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

https://www.acmicpc.net/problem/5052

 

 

이 문제는 N개의 전화번호가 주어졌을때 하나의 전화번호가 다른 하나의 전화번호의 접두어로 포함되어 있는 경우를 찾는 문제이다.

 

이때 전화번호 수가 최대 10000개이며 이때 하나의 전화번호를 선택해서 모든 경우를 탐색하는 경우는 

O(TN^2)으로 1억을 훌쩍 넘겨 시간초과가 난다.

어떻게 풀어야할지 생각이 안나 구글링을 하여 다른 사람들 풀이를 검색하는 와중 트라이(TRIE) 자료구조를 알게 되었다.

 

트라이(TRIE)
문자열을 쉽게 찾을 수 있도록 트리 형태로 구현하는 자료구조로 구조체를 사용하여 쉽게 구현할 수 있다.

자세한 설명은 https://yabmoons.tistory.com/379에서 확인할 수 있다.

 

 

트라이 자료구조를 구현하여 찾을때 문자열끝내는 변수를 확인하여 만약 그 변수가 true인 경우 false를 리턴하여 일관성이 없는것으로 판단한다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

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

    void insert(char *str);
    bool find(const char *str);
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int T, N;
char phone[10001][11];

void TRIE::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 TRIE::find(const char *str) {
    if(*str == NULL) return true;
    if(finish) return false;

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

void solve(TRIE &root) {
    bool flag = true;

    for(int i = 0; i < N; i++) {
        if(flag) flag = root.find(phone[i]);
        if(!flag) break;
    }

    if(flag) {
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N;

        TRIE root;
        for(int i = 0; i < N; i++) {
            cin >> phone[i];
            root.insert(phone[i]);
        }

        solve(root);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}