[BOJ-5052] 전화번호 목록 (C++)

백준 5052 - 전화번호 목록

5052번: 전화번호 목록

 

문제 설명

 

 - 전화번호 목록이 주어지고, 이 전화번호 목록이 일관성을 유지하는지 판단하라.

 

 - 일관성을 유지한다면 YES, 유지하지 않는 다면 NO를 출력한다.

 

 - 일관성을 유지한다는 것은, 한 전화번호가 다른 전화번호의 접두이인 경우가 없다는 것이다.

   (911과 91125426이 있다면, 911은 91125426의 접두어이기 때문에 일관성이 없다.)

 

---

입력 값

 

 - 테스트 케이스 개수 : t (1 <= t <= 50 )

 

 - 전화번호의 수 : n ( 1 <= n <= 10,000)

 

 - 전화번호의 길이 : 최대 10자리

 

 - 같은 전화번호는 주어지지 않는다.

 

 

---

예제

 

---

 

문제 분석

 

 - 해당 전화번호가 다른 전화번호에 접두어인지 판단하면 된다.

 

 - 문자열의 접두어 처리는 트라이 자료구조를 사용하면 편리하게 판단할 수 있다.

 

 

---

 

소스 코드(C++)

 

#include <bits/stdc++.h>
#include <string>

using namespace std;

struct Trie
{
	Trie *childNode[10];
	bool isFinish;

	Trie()
	{
		isFinish = false;
		for (int i = 0; i < 10; i++)
			childNode[i] = NULL;
	}
	~Trie()
	{
		for (int i = 0; i < 10; i++)
		{
			if (childNode[i])
				delete childNode[i];
		}
	}

	void insert(string& str, int i)
	{
		if (str.size() == i)
		{
			isFinish = true;
		}
		else
		{
			int nextNode = str[i] - '0';
			if (childNode[nextNode] == NULL)
			{
				childNode[nextNode] = new Trie();
			}
			childNode[nextNode]->insert(str, i + 1);
		}
	}

	bool find(string& str,int i)
	{
		if (str.size() == i)
		{
			return false;
		}

		if (isFinish)
			return true;

		int nextNode = str[i] - '0';

		return childNode[nextNode]->find(str,i+1);
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t, n;
	string p;
	bool isFinish;
	vector<vector<string>> phone;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n;
		phone.push_back({});

		for (int j = 0; j < n; j++)
		{
			cin >> p;
			phone[i].push_back(p);
			
		}
	}

	for (int i = 0; i < t; i++)
	{
		Trie *root = new Trie();
		for (int j = 0; j < phone[i].size(); j++)
		{

			root->insert(phone[i][j],0);
		}

		isFinish = false;

		for (int j = 0; j < phone[i].size(); j++)
		{

			isFinish = root->find(phone[i][j], 0);
			if (isFinish)
			{
				cout << "NO" << endl;
				break;
			}
		}

		if (!isFinish)
		{
			cout << "YES" << endl;

		}

		delete(root);

	}
	return 0;
}