[백준] 5052번 - 전화번호목록 / C++

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

 

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

 

코드

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

struct TRIE
{
	bool finish;	// 문자열의 끝
	TRIE *next[10];	// 다음 문자에 대한 포인터

	TRIE()
	{
		finish = false;
		memset(next, 0, sizeof(next));
	}

	~TRIE()
	{
		int i;

		for (i = 0; i < 10; i++)
			delete this->next[i];
	}

	// 문자열 s를 삽입
	void insert(string &s, int idx)
	{
		int curr;

		if (idx == s.size())
		{
			finish = true;
			return;
		}
		curr = s[idx] - '0';
		if (next[curr] == NULL)
			next[curr] = new TRIE();
		next[curr]->insert(s, idx + 1);
	}

	// 문자열 s를 검색
	bool find(string &s, int idx)
	{
		int curr;

		if (idx == s.size())
		{
			if (finish)
				return true;
			return false;
		}
		curr = s[idx] - '0';
		if (next[curr] == NULL)
			return false;
		return next[curr]->find(s, idx + 1);
	}
};

int T;
int N;

// 일관성 검사
// 주어진 문자열의 중간에 문자열의 끝이 표시되어 있으면 일관성이 없는 것임
bool check_consistency(TRIE *node, string s)
{
	int i;
	char c;

	for (i = 0; i < 10; i++)
	{
		if (node->next[i])
		{
			if (node->finish)
				return false;
			c = i + '0';
			if (!check_consistency(node->next[i], s + c))
				return false;
		}
	}
	return true;
}

int main()
{
	int i, j;
	string s;
	TRIE *root;
	bool res;

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;
	for (i = 0; i < T; i++)
	{
		cin >> N;
		root = new TRIE();
		for (j = 0; j < N; j++)
		{
			cin >> s;
			root->insert(s, 0);
		}
		res = check_consistency(root, "");
		if (res)
			cout << "YES\n";
		else
			cout << "NO\n";
		delete root;
	}
	return 0;
}

 

트라이(trie) 자료구조를 사용하여 문제를 해결했다. 트라이 자료구조는 문자열을 효율적으로 검색하기 위한 트리 형태의 자료구조이다. 

입력으로 주어진 전화번호를 모두 트라이 자료구조에 저장한다. 이후 저장된 값들을 확인하여 일관성 검사를 한다. 만약 "911"과 "91125426"이 저장된 경우, "911"은 세 번째 "1"에서 끝나지만 "91125426"은 "2"로 이어진다. 이와 같이 다음 노드가 존재하는데 finish == true인 경우 즉 한 번호가 다른 번호의 접두어인 경우 일관성이 없는 것이다.

 

링크

5052번: 전화번호 목록

inbdni/Baekjoon