[BOJ/C++] 전화번호 목록 - 5052번 C++ 풀이

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

5052번: 전화번호 목록

자료구조 트리의 한 종류인 트라이를 사용하여 구현하는 문제

 

#include <bits/stdc++.h>
#include <string.h>
using namespace std;

class Node {
public:
	Node* child[10] = { nullptr, };
	bool finished = false;

	Node() {
		for (int i = 0; i < 10; i++) {
			child[i] = nullptr;
		}
	}
};

class Trie {
public:
	Node* root;
	bool ans;
	Trie() {
		root = new Node();
		ans = true;
	}

	void Insert(Node* cur, const char* str) {
		// 마지막 문자일 경우
		if (*str == '\0') {
			cur->finished = true;
			return;
		}
		else {
			int c = *str - '0';
			if (cur->child[c] == nullptr)
				cur->child[c] = new Node();
			// 현재 노드가 마지막 노드인데 새로 문자가 들어올 경우
			// 123 1234 -> 겹침, but 99999 9은 못잡음 -> sorting함수에서 catch
			if (cur->finished == true) {
				ans = false;
			}
			this->Insert(cur->child[c], str + 1);
		}
	}

	void SortingPrt(Node* cur, string& str) {
		if (cur->finished == true) {
			// cout << str << endl;
			// 위에서 놓친 99999 9 같은 테스트케이스 CATCH
			for (int i = 0; i < 10; i++) {
				if (cur->child[i] != nullptr) {
					ans = false;
				}
			}
		}

		for (int i = 0; i < 10; i++) {
			if (cur->child[i] != nullptr) {
				str += i + '0';
				SortingPrt(cur->child[i], str);
				str.pop_back();
			}
		}
	}
};

int main() {
	int tc; cin >> tc;

	while (tc--) {
		Trie* tr = new Trie();
		string st = "";

		int n; cin >> n;

		for (int i = 0; i < n; i++) {
			string s; cin >> s;
			tr->Insert(tr->root, &s[0]);
		}

		tr->SortingPrt(tr->root, st);

		if (!tr->ans)
			cout << "NO\n";
		else
			cout << "YES\n";

	}

	return 0;
}

입력받을 때 한 번, 정렬 + 출력 하는 함수에서 한 번 검사해줬는데 제대로 짠건지는 잘 모르겠음..