백준 5052번 : 전화번호 목록

문제 접근

---

문자열 알고리즘을 아는게 거의 없어서 고민을 많이 했다. 처음에는 큰 것부터 정렬해서 /10 으로 자릿수 낮춰가며 하나씩 확인하면 되는지 시간 복잡도 계산해보니까 O(1,000,000,000) 이어서 안 될 거 같았다. 알고리즘 분류를 보니 트라이를 사용할 수 있다고 해서 '알고리즘 문제해결전략' 책과 다른 사람 코드를 보면서 구현했다. 

 

트라이 구조체를 만들고 phoneNum 배열에 전화번호를 넣은 뒤 하나씩 find 했을때, phoneNum[i] 탐색이 끝나기 전에 해당 노드의 terminal ( 트라이의 종료 노드라면 true, 아니라면 false. default 값은 false. ) 이 true 라면 1을 반환하여 다른 전화번호의 접두사라는 것을 알린다.

 

 

문제 코드

---

#include <iostream>

using namespace std;

const int NUM = 10;

struct TrieNode
{
	TrieNode* children[NUM];
	bool terminal;
	
	TrieNode():terminal(false)
	{
		for(int i=0; i<NUM; ++i)
			children[i] = nullptr;
	}
	
	~TrieNode()
	{
		for(int i=0; i<NUM; ++i)
			if(children[i] != nullptr)
				delete children[i];
	}
	
	void insert(char* s)
	{
		if(*s == '\0')
			terminal = true;
		
		else
		{
			int next = *s - '0';
			if(children[next] == NULL)
				children[next] = new TrieNode();
			children[next]->insert(s+1);
		}
	}
	
	int find(char* s)
	{
		if(*s == '/0')
			return 0;
		
		if(terminal)
			return 1;
		
		int next = *s -'0';
		return children[next]->find(s+1);
	}
};

int main(void)
{
	int t, n;
	char phoneNum[10001][11];
	
	cin>>t;
	
	while(t--)
	{
		cin>>n;
		
		TrieNode* root = new TrieNode();
		
		for(int i=0; i<n; ++i)
		{
			cin>>phoneNum[i];
			root->insert(phoneNum[i]);
		}
		
		bool flag = true;
		
		for(int i=0; i<n; ++i)
			if(root->find(phoneNum[i]))
			{
				flag = false;
				break;
			}
		
		if(flag)
			cout<<"YES\n";
		
		else
			cout<<"NO\n";
		
		delete root;
	}
}