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

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

5052번: 전화번호 목록

문제

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

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

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

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

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

입력

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

출력

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

---

트라이 자료구조로 풀 수 있는 문제였다. 트라이 자료구조를 아느냐 모르냐로 문제 난이도가 극명하게 갈릴 것 같다. 입력을 우선 모두 다 받은 다음 트라이의 중간에 Finish 가 true인 경우에는 일관성이 없는 목록이 되므로 NO를 출력하도록 한다.

#include <iostream>
#include <string>

using namespace std;

char input[10000][11];

struct TRIE {
	
	bool Finish;
	TRIE *Node[10];
	TRIE() {
		Finish = false;
		for (int i = 0; i < 10; i++) {
			Node[i] = NULL;
		}
	}

	void insert(char *str) {
		if (*str == '\0') {
			Finish = true;
			return;
		}
		int Cur = *str - '0';
		if (Node[Cur] == NULL) Node[Cur] = new TRIE();
		Node[Cur]->insert(str + 1);
	}

	bool find(char *str) {
		if (*str == '\0') {
			return false;
		}
		if (Finish == true)
			return true;

		int Cur = *str - '0';
		if (Node[Cur] == NULL) return false;
		return Node[Cur]->find(str + 1);
	}


};


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

	

	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		TRIE *Root = new TRIE();
		for (int i = 0; i < n; i++) {
			cin >> input[i];
			Root->insert(input[i]);
		}
		int i;
		for(i=0; i<n;i++){
			if (Root->find(input[i])) {
				cout << "NO\n";
				break;
			}
		}
		if (i == n)
			cout << "YES\n";
	}

	return 0;
}

---

트라이 자료구조를 공부해볼겸 추천 문제를 풀어보았다. 내 나름대로 코드를 변형해서 구현해보았는데 남들과 같이 25퍼센트에서 시간 초과가 낫다. 사용한 개념은 비슷한 것 같은데 왜 안되는지는 잘 모르겠다! 트라이 구조체를 사용할 때 구조체 내부 메서드를 사용하는 것부터 되게 낯선데 트라이 문제를 조금 더 연습해보아야겠다!