[BOJ] 5052번 전화번호 목록

문제 바로가기

접근

이 문제를 풀면서 Trie라는 자료구조를 처음 알게 되었다. Trie는 문자열을 트리에 효율적으로 저장해 문자열을 검색하는 데 O(L)(L=문자열의 길이)만이 걸린다.

한 노드에 달린 모든 자식들은 루트로부터 해당 노드까지에 이르는 문자열을 접두어로 가지고 있다는 특징이 있다.

#include <bits/stdc++.h>
using namespace std;

#define NUMBER 10
#define MAX 10000

struct Trie {
  bool is_terminal;
  Trie *children[NUMBER];

  Trie(): is_terminal(false) {
    memset(children, 0, sizeof(children));
  }

  ~Trie() {
    for(int i = 0; i < NUMBER; i++) {
      if(children[i])
        delete children[i];
    }
  }

  void insert(char *key) {
    if(*key == '\0') {
      is_terminal = true;
      return;
    }

    int idx = *key - '0';
    if(children[idx] == 0)
      children[idx] = new Trie();

    children[idx]->insert(key + 1);
  }

  bool find(char *key) {
    if(*key == '\0')
      return true;

    if(is_terminal)
      return false;

    int idx = *key - '0';
    return children[idx]->find(key + 1);
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  int T, N;
  char tmp[MAX][11];
  bool inconsistent;
  Trie *ptr;

  cin >> T;
  for(int i = 0; i < T; i++) {
    cin >> N;
    ptr = new Trie();
    inconsistent = false;

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

    for(int j = 0; j < N; j++) {
      if(!ptr->find(tmp[j])) {
        inconsistent = true;
        break;
      }
    }

    delete ptr;

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