백준 5052번 전화번호 목록 문제풀이 (C++)

백준 5052번 전화번호 목록

아이디어

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

해당 문자열을 입력중에 다른 문자열이 완성되면 안된다 -> 트라이 알고리즘의 개념 이용 -> 트라이 알고리즘 : 트리의 개념을 이용한 문자열 탐색 알고리즘

방법 : 
	1.문자열 입력시 해당 문자열을 TRIE로 만들고 마지막을 finish처리
    	2.문자열 탐색시 null이 아닌 finish == true를 먼저 만나면 접두어인 경우 == false

문제풀이

#include<bits/stdc++.h>
using namespace std;
char input[10000][11];
struct TRIE {
	bool Finish;
	TRIE* Node[10];
	TRIE() {
		Finish = false;
		for (int i = 0; i < 10; i++) {
			Node[i] = NULL;
		}
	}
	void insert(char* str) {
		if (*str == '\0') {
			Finish = true;
			return;
		}
		int Cur = *str - '0';
		if (Node[Cur] == NULL) Node[Cur] = new TRIE();
		Node[Cur]->insert(str + 1);
	}

	bool find(char* str) {
		if (*str == '\0') {
			return false;
		}
		if (Finish == true)
			return true;

		int Cur = *str - '0';
		if (Node[Cur] == NULL) return false;
		return Node[Cur]->find(str + 1);
	}
};
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t, n; cin >> t;
	while (t--) {
		cin >> n;
		TRIE* Root = new TRIE();
		for (int i = 0; i < n; i++) {
			cin >> input[i];
			Root->insert(input[i]);
		}
		int i;
		for (i = 0; i < n; i++) {
			if (Root->find(input[i])) {
				cout << "NO\n";
				break;
			}
		}
		if (i == n)
			cout << "YES\n";
	}
	return 0;
}