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

문제 링크: https://www.acmicpc.net/problem/5052

 

여러 풀이가 있겠는데, 트라이(trie)로 풀 수 있습니다.

일단 트라이를 쭉 완성합니다. 문자열갖고 트라이를 만들 때 문자열의 끝부분에 해당되는 노드마다 끝부분이라고 체크를 해줍니다.

그 다음, dfs로 트라이를 한번 쭉 순회를 하는데 끝부분이라고 체크가 되어 있으면서 자식 노드가 있는 노드가 있으면 일관성이 없게 됩니다.

 

트라이를 배열로 구현해서 풀었습니다. 동적할당은 귀찮네요.

트라이 관련 내용은 나중에 게시물로 정리해서 올릴 예정입니다.

#include <bits/stdc++.h>
using namespace std;

int trie[100001][10];
bool terminating[100001];
int trie_size;

void trie_insert(const string& s) {
	auto sz = s.size();
	assert(sz <= 10);

	int node = 0;
	for (auto& c : s) {
		if (trie[node][c - '0'] == 0) {
			trie[node][c - '0'] = ++trie_size;
			node = trie_size;
		}
		else
			node = trie[node][c - '0'];
	}

	terminating[node] = true;
}

bool consistent(int node) {
	if (terminating[node] && accumulate(trie[node], trie[node]+10, 0) != 0)
		return false;

	bool ret = true;
	for (int i=0; i<10; ++i)
		if (trie[node][i])
			ret &= consistent(trie[node][i]);

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) {
		memset(trie, 0, sizeof(trie));
		memset(terminating, 0, sizeof(terminating));
		trie_size = 0;

		int n;
		cin >> n;

		string s;
		while (n--) {
			cin >> s;
			trie_insert(s);
		}

		cout << (consistent(0) ? "YES\n" : "NO\n");
	}
	
	return 0;
}

위에서 설명한대로 짠 버전입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int trie[100001][10];
int trie_size;
bool consistency;

void trie_insert(const string& s) {
	auto sz = s.size();
	assert(sz <= 10);

	int node = 0;
	for (auto& c : s) {
		if (trie[node][c - '0'] == 0) {
			trie[node][c - '0'] = ++trie_size;
			node = trie_size;
		}
		else
			node = trie[node][c - '0'];
	}

	int next_cnt = 0;
	for (int i = 0; i < 10; ++i)
		next_cnt += (trie[node][i] != 0);

	if (next_cnt)
		consistency = false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) {
		memset(trie, 0, sizeof(trie));
		consistency = true;
		trie_size = 0;

		int n;
		cin >> n;
		vector<string> vs(n);
		for (auto& s : vs)
			cin >> s;
		// 길이순 정렬 (내림차순)
		sort(vs.begin(), vs.end(), [](string& s1, string& s2){return s1.size() > s2.size();});

		for (auto& s : vs)
			trie_insert(s);

		cout << (consistency ? "YES\n" : "NO\n");
	}
	
	return 0;
}

배열로 구현한 트라이 쓴 건 같은데, 전화번호를 다 입력받고 길이 내림차순으로 정렬한 뒤 트라이를 만들면서 일관성 여부를 체크한 버전입니다.

원래 이 버전을 짠 다음에 문자열 정렬을 굳이 안해도 될 것 같아서 위에 버전으로 다시 짰는데, 밑에 버전이 더 빠르네요?

재귀를 안써서 그런가.. 뭐 모르겠습니다.