[백준 5052번] 전화번호 목록

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

5052번: 전화번호 목록

<문제 풀이> 트라이(trie)

 

트라이를 사용하여 전화번호를 삽입합니다. 삽입할 때마다, 트라이 내에 전화번호의 접두사가 이미 존재하는지 확인해야 합니다.

이를 구현하기 위해서는 find 함수에서 각 노드의 자식 노드의 존재 여부와 전화번호의 끝을 체크해야 합니다.

 

 

<C++소스코드>

 

#include<iostream>
#include<cstring>
using namespace std;

class Trie {
public:
	static const int MX = 10000 * 10;
	static const int ROOT = 1;
	int unused = 2;
	int nxt[MX + 1][10];
	bool check[MX + 1];

	Trie() {
		memset(nxt, 0xff, sizeof(nxt));
		memset(check, 0x00, sizeof(check));
	}
	void insert(const string &s) {
		int cur = ROOT;
		for (auto& c : s) {
			if (nxt[cur][c - '0'] == -1) nxt[cur][c - '0'] = unused++;
			cur = nxt[cur][c - '0'];
		}
		check[cur] = true;
	}
	bool find(const string& s) {
		int cur = ROOT;
		for (auto& c : s) {
			cur = nxt[cur][c - '0'];
			if (cur == -1) return false;
			else if (check[cur]) return true;
		}
		return true;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int test_case; cin >> test_case;
	while (test_case--) {
		int n; cin >> n;
		string ans = "YES";
		Trie *trie = new Trie();
		for (int i = 0; i < n; i ++) {
			string num; cin >> num;
			if (trie->find(num)) ans = "NO";
			trie->insert(num);
		}
		cout << ans << '\n';
	}

	return 0;
}