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

Problem

---

Solution

접두사를 통해 해결할 수 있는 문제이므로 트라이를 이용한다.

트라이를 통해 일관성 없는 전화번호 목록을 어떻게 찾을 수 있을까?

트라이에서 두 문자열이 같은 접두사를 공유하고 있으면 같은 노드를 공유하고 있다.

 

예를 들어 두 문자열 913, 9134가 트라이에 입력되었을 때,  두 문자열은 9, 91, 913 노드를 공유하고 있다.

 

이때 공유하는 노드 중에 문자열의 끝을 나타내는 노드가 있으면 일관성이 없는 전화번호 목록이라고 볼 수 있다.

 

이 예제에서는 913 노드가 문자열의 끝을 나타내는 노드이므로 913, 9134는 일관성이 없는 전화번호 목록이다.

1. 모든 전화번호를 트라이에 넣는다.

 

2. 각각의 전화번호를 트라이에서 탐색하면서 일관성 여부를 확인한다.

 

3. 마지막 전화번호까지 일관성 여부 검사를 통과하면 일관성이 있는 전화번호 목록이다!

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int ALPAHBET_SIZE = 10;

typedef struct trieNode {
	struct trieNode* children[ALPAHBET_SIZE];
	bool isEndOfWord;
} TrieNode;

TrieNode* newNode() {
	TrieNode* pNode = new TrieNode;
	
	pNode -> isEndOfWord = false;
	for(int i=0; i<ALPAHBET_SIZE; i++){
		pNode->children[i] = NULL;
	}

	return pNode;
}

void insert(TrieNode* root, string key) {
	TrieNode* pCrawl = root;

	int len = key.length();
	for(int i=0; i<len; i++) {
		int index = key[i] - '0';
		if(pCrawl->children[index] == NULL) {
			pCrawl->children[index] = newNode();
		}

		pCrawl = pCrawl->children[index];
	}

	pCrawl->isEndOfWord = true;
}

bool hasConsistency(TrieNode* root, string key) {
	TrieNode* pCrawl = root;

	int len = key.length();
	for(int i=0; i<len; i++) {
		int index = key[i] - '0';
		if(pCrawl->isEndOfWord) return false;
		pCrawl = pCrawl->children[index];
	}

	return true;
}

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

	int t;
	cin>>t;
	while(t--) {
		int n;
		cin>>n;

		vector<string> arr(n);
		for(int i=0; i<n; i++){
			cin>>arr[i];
		}

		// 트라이에 모든 전화번호를 집어넣는다
		TrieNode* root = newNode();

		for(int i=0; i<n; i++) {
			insert(root, arr[i]);
		}

		// 트라이에서 각각의 전화번호를 탐색하면서
		// 일관성 여부를 확인한다
		int i;
		for(i=0; i<n; i++) {
			if(!hasConsistency(root, arr[i])) break;
		}

		if(i == n) {
			cout<<"YES\n";
		}
		else {
			cout<<"NO\n";
		}
	}
}

Trie 코드는 아래의 사이트를 참고하였다.

Trie | (Insert and Search) - GeeksforGeeks

 

---

Result

처음에는 전화번호를 int형 변수로 처리하였다. 그러나 0으로 시작하는 전화번호의 경우 0을 무시해버리기 때문에 전화번호를 문자열로 처리하여 문제를 해결할 수 있었다.