백준 5052번: 전화번호 목록

[문제 링크]

5052번: 전화번호 목록

---

트라이 자료구조를 활용하는 문제였다.

우선 전화번호 목록을 트라이에 담으면서 전화번호의 끝자리인 노드를 체크하였다.

그다음, 완성된 트라이에서 전화번호를 검색하여 끝자리에 도달하기 전에 다른 전화번호의 끝자리인 노드에 방문하게 되는지 여부를 판단하여 입력받은 전화번호 목록이 일관성 있는 목록인지 아닌지를 알 수 있다.

---

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

const int NUMBER = 10;

class TrieNode {
	TrieNode* children[NUMBER];
	bool terminal;

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

	void insert(string& key, int here) {
		if (here == key.size()) 
			terminal = true;
		else {
			int next = key[here] - '0';
			if (children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(key, here + 1);
		}
	}

	bool find(string& key, int here) {
		if (here == key.size()) return true;
		
		if (this->terminal)
			return false;

		int next = key[here] - '0';
		return children[next]->find(key, here + 1);
	}
};

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int t;
	cin >> t;
	
	while (t--) {
		int n;
		cin >> n;

		vector<string> numberList(10001);
		TrieNode* trie = new TrieNode();

		for (int i = 0; i < n; i++) {
			string num;
			cin >> num;
			numberList[i] = num;
			trie->insert(num, 0);
		}

		bool flag = true;
		for (int i = 0; i < n; i++) {
			if (!trie->find(numberList[i], 0)) {
				cout << "NO" << '\n';
				flag = false;
				break;
			}
		}
		if (flag)
			cout << "YES" << '\n';

		delete trie;
	}
}