백준 5052 전화번호 목록
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int NUMBER_SIZE = 10;
struct TrieNode{
struct TrieNode *children[NUMBER_SIZE];
bool isEndOfWord;
};
struct TrieNode *getNode(void){
struct TrieNode *pNode = new TrieNode;
pNode->isEndOfWord = false;
for (int i = 0; i < NUMBER_SIZE; i++)
pNode->children[i] = NULL;
return pNode;
}
void insert(struct TrieNode *root, string key){
struct TrieNode *pCrawl = root;
for (int i = 0; i < key.length(); i++)
{
int index = key[i] - '0';
if (!pCrawl->children[index])
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
}
pCrawl->isEndOfWord = true;
}
int search(struct TrieNode *root, string key){
struct TrieNode *pCrawl = root;
for (int i = 0; i < key.length(); i++)
{
int index = key[i] - '0';
if (!pCrawl->children[index])
return -1;
pCrawl = pCrawl->children[index];
}
return (pCrawl->isEndOfWord);
}
bool cmp(string a, string b) {
return a.length() > b.length();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<string> keys;
for (int i = 0; i < n; ++i) {
string input;
cin >> input;
keys.push_back(input);
}
sort(keys.begin(), keys.end(), cmp);
struct TrieNode *root = getNode();
bool flag = true;
for (int i = 0; i < n; i++) {
if (search(root, keys[i]) != -1) {
cout << "NO\n";
flag = false;
break;
}
insert(root, keys[i]);
}
if (flag) cout << "YES\n";
}
return 0;
}