BOJ 5052 - 전화번호 목록

Problem
https://www.acmicpc.net/problem/5052

Solution

문자열 분류 문제들을 풀던 중, 위 문제를 만났다.

알고보니 Trie라는 자료구조를 사용해서 풀이하는 문제였다.

Trie는 문자열이 다른 문자열의 접두사에 해당하는지 확인하는데에 최적화 되어있는 자료구조이다.

이 Trie자료구조만 알고있다면, 그대로 사용하면 문제는 풀리는 수준이기에 어렵지 않다.

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

const int SIZE = 10;
bool possible;

struct TrieNode {
	TrieNode* Node[SIZE];
	bool isEnd;
	
	TrieNode() {
		isEnd = false;
		for (int i = 0; i < SIZE; i++) Node[i] = nullptr;
	}

	void Insert(const string& key, int index) {

		if (index == key.length()) {
			isEnd = true;
			return;
		}

		if (isEnd) {
			possible = false;
		}

		else {
			int next = key[index] - '0';
			if (Node[next] == nullptr) {
				Node[next] = new TrieNode();
			}
			Node[next]->Insert(key, index + 1);

		}
	}
};


int main(void) {

	int t;
	cin >> t;

	while(t--) {
		int n;
		string str;
		TrieNode root;
		vector<string> vs;

		possible = true;

		cin >> n;

		for (int i= 0; i < n; i++) {
			cin >> str;
			vs.push_back(str);
		}
		sort(vs.begin(), vs.end());

		for (auto val : vs) {
			root.Insert(val,0);
		}

		if (possible) cout << "YES\n"; //일관성 o
		else cout << "NO\n"; //일관성 x
	}

	return 0;
}

여기서 하나 짚고가야할 점이 있는데, sort 부분이다.

예제로 들어오는 값이
18
1818
일 경우에는 sort가 없어도 잘 작동한다.

1818의 경우에는 재귀로 탐색중에 18이라는 문자열이 존재한다는것을 알 수 있기 때문이다.

하지만 반대로
1818
18
이 들어왔을 경우에는 18이 1818의 접두사가 됨에도 불구하고, 문자열이 더 짧기에 제대로 판단할 수 없다 . (마지막 8에서만 판단이 가능하기 때문에)

그래서 접두사가 같은 경우 sort로 짧은 문자열부터 넣을수있도록 설정이 필요한것이다.