BOJ5052 전화번호 목록

논리

단어를 추가하면서 아직 삽입이 끝나지 않았음에도 지나간 노드 중에 isEnd가 포함된 노드가 있는지 체크한다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Trie {
private: 
	bool isEnd = false;
	Trie* child[10];

public:
	Trie(): child(){}

	void Insert(string phnum) {
		Trie* now = this; 
		for (int i = 0; i < phnum.length(); ++i)
		{
			if (now->child[phnum[i] - '0'] == nullptr)
				now->child[phnum[i] - '0'] = new Trie(); 
			now = now->child[phnum[i] - '0'];
			if (i == phnum.length() - 1) now->isEnd = true; 
		}
	}
	bool isTherePrefix(string phnum) {
		Trie* now = this; 
		for (int i = 0; i < phnum.length(); ++i)
		{
			if (now->child[phnum[i] - '0'] != nullptr) {
				now = now->child[phnum[i] - '0']; 
				if (now->isEnd) 
					return true;
			}
			else
				return false;
		}
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t, n;
	cin >> t;

	for (int i = 0; i < t; i++){
		cin >> n;
		vector<string> phnum_list(n);
		for (int j = 0; j < n; j++){
			cin >> phnum_list[j];
		}
		sort(phnum_list.begin(), phnum_list.end());
		Trie* trie = new Trie();
		bool ok = true;
		for (auto phnum : phnum_list) {
			if (trie->isTherePrefix(phnum)) { 
				ok = false;
				break;
			}
			trie->Insert(phnum); 
		}
		if (ok) cout << "YES" << '\n';
		else cout << "NO" << '\n';
	}
}

//https://ansohxxn.github.io/boj/5052/