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

문제 링크

5052번: 전화번호 목록

문제 요약

주어진 전화 번호 중에 어떠한 전화번호가 다른 전화번호의 접두어가 되는 경우가 있는지 판별해야 한다.

접근 방법

트라이를 이용해서 풀었습니다. 먼저 입력으로 주어진 전화번호들을 모두 트라이에 집어 넣습니다. 그 다음에 각 전화번호로 순서대로 트라이에서 탐색을 합니다. 만약에 전화번호의 맨 마지막 번호에 해당하는 노드에 도달했을때, 자식 노드가 존재한다면 해당 전화번호는 다른 전화번호의 접두어가 될 수 있습니다.

트라이를 오늘 처음 공부했는데, KMP같은 다른 문자열 알고리즘보다는 이해하기 쉬워서 재밌게 푼 것 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Trie {
	Trie* child[10];

	Trie() {
		for (int i = 0; i < 10; i++)
			child[i] = NULL;
	}

	void insert(string& numbers, int idx) {
		if (idx == numbers.size())
			return;

		if (child[numbers[idx] - '0'] == NULL) {
			Trie* trie = new Trie();
			child[numbers[idx] - '0'] = trie;
		}

		child[numbers[idx] - '0']->insert(numbers, idx + 1);
	}

	bool check(string& numbers, int idx) {
		if (idx == numbers.size()) {
			for (int i = 0; i < 10; i++)
				if (child[i] != NULL)
					return false;
			return true;
		}

		if (!child[numbers[idx] - '0']->check(numbers, idx + 1))
			return false;
		return true;
	}

	void clear(void) {
		for (int i = 0; i < 10; i++) {
			if (child[i] != NULL) {
				child[i]->clear();
				delete child[i];
			}
		}
	}
};

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;

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

		Trie* root = new Trie();

		vector<string> v(n);
		for (int i = 0; i < n; i++)
			cin >> v[i];
		
		for (auto& i : v)
			root->insert(i, 0);

		bool flag = false;
		for (auto& i : v) {
			if (!root->check(i, 0)) {
				flag = true;
				break;
			}
		}

		cout << (flag ? "NO\n" : "YES\n");
		root->clear();
		delete root;
	}

	return 0;
}