[BOJ] 5052 : Phone List

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

---

트라이 trie 문자열

 자료구조 트라이를 이용해서 문자열을 다 insert 해놓은 후, 모든 Input 문자열에 대해서 find를 진행하며, 해당 문자열 탐색이 끝나기 전에 terminal 이 true인 상황이 발생하면 다른 완성된 문자열이 탐색된 것이므로 NO를 출력하고 아니라면 YES를 출력한다.

#include<iostream>
#include<string>
#include<vector>
#include<cstdlib>
using namespace std;

struct TrieNode {
	TrieNode* child[10];
	bool terminal;

	TrieNode() : terminal(false) {
		memset(child, 0, sizeof(child));
	}
	~TrieNode() {
		for (int i = 0; i < 10; i++)
			if (child[i])
				delete child[i];
	}

	void insert(const char* key) {
		if (*key == 0)
			terminal = true;
		else {
			int next = (*key - '0');
			if (child[next] == NULL)
				child[next] = new TrieNode();
			child[next]->insert(key + 1);
		}
	}

	bool find(const char* key) {
		if (*key == 0)
			return false;
		if (terminal)
			return true;
		int next = (*key - '0');
		if (child[next] == NULL)
			return false;
		return child[next]->find(key + 1);
	}
};

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

	int t;
	cin >> t;
	while (t--) {
		int n;
		TrieNode* trie = new TrieNode();
		vector<string> input;
		cin >> n;
		for (int i = 0; i < n; i++) {
			string temp;
			cin >> temp;
			input.push_back(temp);
			trie->insert(temp.c_str());
		}
		bool flag = false;
		for (int i = 0; i < n; i++) {
			if (trie->find(input[i].c_str()) == true) {
				flag = true;
				break;
			}
		}
		if (flag) cout << "NO\n";
		else cout << "YES\n";
	}
}

---