백준 5052번

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

해당 문제는 크게 어렵지는 않았다. trie의 특성을 이용해서 쉽게해결할 수 있다. 우선 문제를 해결하려면 현재의 온전한 문자를 접두사로 사용하는 곳이 있는지 체크해주어야한다. 트라이의 특성을 이용해 이 값을 다 찾으 다음 다음 후보군 노드 중에 NULL이 아닌 값이 있으면 해당 문자가 접두사로 이용되고 있음을 뜻한다. 

 

아래 그림을 보면 간단할 것이다. 

911을 찾을 때 911까지 찾은 후 다음 노드가 있는지 0 ~ 9까지 반복을 통해 체크해주었다. 

 

정답

#include <cstdio>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
int testCase;

using namespace std;

void solve();
int toIndex(char num){
	return num - '0';
}

typedef struct TrieNode{
	bool isTerminal;
	TrieNode *children[11];

	TrieNode():isTerminal(false){
		memset(children, 0, sizeof(children));
	}

	~TrieNode(){
		for(int i = 0; i < 10; i++)
			if(children[i] != NULL)
				delete children[i];
	}

	void insert(char *words){
		if(*words == 0)
			isTerminal = true;
		else{
			int next = toIndex(*words);

			if(children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(words+1);
		}
	}

	int find(const char *words){
		int next = toIndex(*words);
		if(*(words+1) == 0){
			for(int i = 0; i < 10; i++)
				if(children[next]->children[i] != NULL){
					return 1;
				}

				return 0;
		}else
			return children[next]->find(words+1);
	}
}Trie;

int main(){
	scanf("%d", &testCase);

	for(int i = 0; i < testCase; i++){
		solve();
	}
}

void solve(){
	int N;
	char words[12];
	vector<string> wordsSet;
	scanf("%d", &N);

	TrieNode* root = new TrieNode();

	for(int i = 0; i < N; i++){
		scanf("%s", &words);
		root->insert(words);
		wordsSet.push_back(string(words));
	}

	sort(wordsSet.begin(), wordsSet.end());
	

	for(int i = 0; i < N; i++){
		if(root->find(wordsSet[i].c_str())){
			printf("NO\n");
			return ;
		}		
	}
	printf("YES\n");
}