BOJ 5052 - 전화번호 목록 (Trie)

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

트라이 기본문제. trie구조체의 find함수를 변형해서 풀면 된다.

 

<문제설명>

트라이에 문자열들이 들어있을 때, 어떤 문자열이 다음 노드를 가지면서 term=true라면 NO를, 아니면 YES를 출력하는 문제.

 

<풀이>

1.트라이 구조를 하나 만들어 둔다.

Trie* root = new Trie();

 

2. find를 변형한 isConsistent를 짠다.

bool isConsistent(char* key) {
	if (*key == 0) return 1;
	if (term) return 0;
	int c = *key - '0';
	return next[c]->isConsistent(key + 1);
}

무사히 끝까지 탐색했다면 consistent한 전화번호부이다.

끝까지 탐색하기 전에 종료표시(term=true)된 노드가 있다면 inconsistent한 전화번호부이다.

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 4;
struct Trie {
	Trie* next[10];
	bool term;
	Trie() {
		term = false;
		for (int i = 0; i < 10; i++)
			next[i] = NULL;
	}
	~Trie() {
		for (int i = 0; i < 10; i++)
			if (!next[i]) delete next[i];
	}
	void insert(char* key) {
		if (*key == 0) {
			term = true;
			return;
		}
		int c = *key - '0';
		if (next[c] == NULL) next[c] = new Trie();
		next[c]->insert(key + 1);
	}
	bool isConsistent(char* key) {
		if (*key == 0) return 1;
		if (term) return 0;
		int c = *key - '0';
		return next[c]->isConsistent(key + 1);
	}
};

char a[MAX][12];
int main() {
	int tt; cin >> tt;
	while (tt--) {
		int n; cin >> n;
		for (int i = 0; i < n; i++)
			cin >> a[i];
		Trie* root = new Trie();
		for (int i = 0; i < n; i++)
			root->insert(a[i]);

		bool flag = true;
		for (int i = 0; i < n; i++)
			if (!root->isConsistent(a[i])) flag = false;

		cout << (flag ? "YES\n" : "NO\n");
	}
}