BOJ 백준 5052 : 전화번호 목록

시작하면서

　이번 문제는 트라이(Trie) 문제이다. 트라이는 주로 검색 알고리즘에 쓰인다고 한다. 처음보는 개념이었고, 공부 후에 문제에 맞게 구현해서 이 문제를 해결했다.

BOJ 5052 - 전화번호 목록

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 3가지이다.

• t : 테스트 케이스 개수
• n : 전화번호의 수
• number : 전화번호

​

문제 아이디어

　해당 문제의 핵심 포인트는 패턴이 겹치지 않아야 한다. 그말은 쉽게 풀자면 짧은 번호로 시작되는 다른 번호가 존재하면 일관성 있는 목록이 아닌 것이다.

​ 문제를 푸는 방법은 다음과 같다.

1. 전화번호를 받으면서 트라이(Trie)에 넣는다.
2. 일관성 있는 값이 아닌 경우는 다음 2가지가 있다.
   • 값을 넣던 도중에 해당 값이 이전에 존재했고, 트라이의 leaf인 경우
   • 마지막 숫자를 넣었는데 해당 값이 leaf가 아니고, 해당 값의 다음 값이 존재하는 경우

​ 해당 조건들을 기준으로 문제를 푸는데 주의할 점이 있다. 전화번호가 0으로 시작할 수도 있고, 0으로 끝날 수도 있으므로 인풋을 받을 때 int가 아닌 string을 사용해야 한다.

​

해결

#include <iostream>
#include <string.h>
#include <string>
#include <cmath>

using namespace std;

#define NUMBER_LENGTH (10)

/*
	CLASS
*/

class Trie
{
private:
	bool m_isTerminal;
	bool m_isNextExist;
	Trie* m_node[NUMBER_LENGTH];
public:
	Trie()
	{
		this->m_isTerminal = false;
		this->m_isNextExist = false;

		memset(this->m_node, NULL, sizeof(this->m_node));
	}

	~Trie()
	{
		Clear();
	}

	void Clear()
	{
		this->m_isTerminal = false;

		for (int i = 0; i < NUMBER_LENGTH; i++)
		{
			if (this->m_node[i])
			{
				delete this->m_node[i];
			}
		}

		memset(this->m_node, NULL, sizeof(this->m_node));
	}

	bool Insert(const int* key, int digitCount);
	Trie* Find(const int* key);
	bool IsExist(const int* key);
};


bool Trie::Insert(const int* key, int digitCount)
{
	if (digitCount == 0)
	{
		if (this->m_isNextExist == true)
			return false;

		this->m_isTerminal = true;

		return true;
	}
	else
	{
		int index = *key;

		if (this->m_node[index] == NULL)
		{
			this->m_node[index] = new Trie();
		}
		else if (this->m_node[index]->m_isTerminal == true)
		{
			return false;
		}

		this->m_isNextExist = true;

		return this->m_node[index]->Insert(key + 1, --digitCount);
	}
}

Trie* Trie::Find(const int* key)
{
	if (*key == 0)
		return this;

	int index = *key;

	if (this->m_node[index] == 0)
		return NULL;
	else
		return this->m_node[index]->Find(key + 1);
}

bool Trie::IsExist(const int* key)
{
	if (*key == 0 && this->m_isTerminal == true)
		return true;

	int index = *key;

	if (this->m_node[index] == 0)
		return false;
	else
		return this->m_node[index]->IsExist(key + 1);
}

/*
	FUNCTION
*/
int GetDigitCountOfNumber(int number)
{
	if (number < 0)
		return -1;

	int count = 0;

	while (number > 0)
	{
		number /= 10;
		count++;
	}

	return count;
}

int* GetNumberArrayOfNumber(int number, int digitCount)
{
	if (digitCount > NUMBER_LENGTH)
		return NULL;

	int* arr = new int[digitCount];
	int count = 0;

	while (number != 0)
	{
		arr[digitCount - 1 - count] = number % 10;

		count++;
		number /= 10;
	}

	return arr;
}

int* GetNumberArrayOfString(string str)
{
	int* arr = new int[str.length()];

	for (int i = 0; i < str.length(); i++)
	{
		arr[i] = str[i] - '0';
	}

	return arr;
}

int main()
{
	int t, n;
	Trie* trie = new Trie();

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n;

		int number = 0;
		bool result = true;

		for (int j = 0; j < n; j++)
		{
			string str;

			cin >> str;						

			if (result == false)
				continue;

			int* numberArray = GetNumberArrayOfString(str);

			if (trie->Insert(numberArray, str.length()) == false)
			{
				result = false;
			}

			delete[] numberArray;
		}

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

		trie->Clear();
	}

	delete trie;

	return 0;
}

​

마치며

　코드에 보면 사용하지 않는 코드들도 끼어있을 것이다. Trie를 구현하면서 필요한 함수를 넣은 것도 있고, 처음에 풀 때 int를 인풋으로 받아서 사용했던 함수도 있다. (문제 이해를 잘 하자… 0이 앞 뒤로 나올줄이야…)

​ 일상생활에서 많이 사용하는 검색에 관련된 알고리즘 개념을 공부해서 푼 문제라 상당히 유익했고, 시간 있을 때 더 고도화된 문제도 풀어보면 좋을듯하다.