백준 온라인저지 5052 번 전화번호 목록

TRIE 를 비교적 쉽게 풀 수 있었던 문제 

 

TRIE 를 쓰지 않으면 , 전체 스트링을 비교해야 되니까? O(n^2) 의 알고리즘이 

 

TRIE 를 써서  O(n) 의 속도로 줄어들 은 것 같다. 

 

처음에는 add 를 하면서 바로 NO 인 케이스를 발견해내는 방법으로 진행했는 데

 

12345 가 들어오고 123 이 들어오면 괜찮으나 반대로 123 이 들어오고 12345 가 

 

들어오면 구현이 어려워지는 문제점이 있어서 다른 곳에서 본 대로 , 먼저 add 로 

 

전부 저장해 놓은 후에 , 추후에 find 를 해가면서 NO 를 발견하는 구조로 갔다. 

 

#include  using namespace std; #define INTEGER_NUM 10 #define MAX_TREE_SIZE 2000000 #define MAX_NUM 10000 struct NODE { bool isWord; NODE* children[INTEGER_NUM]; }nodes[MAX_TREE_SIZE]; int nodes_cnt = 0; NODE* myalloc() { for (int i = 0; i < INTEGER_NUM; i++) { nodes[nodes_cnt].children[i] = NULL; } nodes[nodes_cnt].isWord = false; return &nodes[nodes_cnt++]; } void add(NODE* root, char* str) { NODE* c = root; for (int i = 0; str[i]; i++) { int nextIdx = str[i] - '0'; if (c->children[nextIdx]) { c = c->children[nextIdx]; } else { NODE* newNode = myalloc(); c->children[nextIdx] = newNode; c = c->children[nextIdx]; } } c->isWord = true; } int find(NODE* root, char* str) { NODE* c = root; for (int i = 0; str[i]; i++) { if (c->isWord == true) return 0; int nextIdx = str[i] - '0'; c = c->children[nextIdx]; } return 1; } void init() { nodes_cnt = 0; } int canAdd() { int wordCnt; char inputStr[MAX_NUM][11]; NODE* root = myalloc(); cin >> wordCnt; for (int i = 0; i < wordCnt; i++) { cin >> inputStr[i]; add(root, inputStr[i]); } for (int i = 0; i < wordCnt; i++) { if (!find(root, inputStr[i])) return 0; } return 1; } int main() { int total; cin >> total; for (int i = 0; i < total; i++) { // 초기화  init(); if (!canAdd()) cout << "NO" << endl; else cout << "YES" << endl; } }