[PS] 전화번호 목록 / C++ (백준 5052번)

 

 

자료구조 트라이(Trie) 기초 문제로 해시 테이블을 사용해서 풀 수도 있는 문제

 

Trie를 문제에 맞게 구현해주면 쉽게 풀 수 있다.

• insert 도중 finish가 true면 일관성 X
• insert가 끝난 후 finish에 true 값을 저장하려는데 number 배열이 비어있지 않으면 일관성 X 

 

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

struct Trie {
	bool finish;
	Trie* number[10];

	Trie() :finish(false) {
		memset(number, 0, sizeof(number));
	}

	~Trie() {
		for (int i = 0; i < 10; i++) {
			if (number[i])delete(number[i]);
		}
	}

	bool insert(char* key) {
		if (finish == true) {
			return false;
		}
		if (*key == '\0') {
			finish = true;
			for (int i = 0; i < 10; i++) {
				if (number[i] != NULL) {
					return false;
				}
			}
			return true;
		}
		int cur = *key - '0';
		if (number[cur] == NULL) {
			number[cur] = new Trie();
		}
		return number[cur]->insert(key + 1);
	}
};

int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		int n;
		scanf("%d", &n);
		Trie* tree = new Trie();
		bool f = true;
		for (int j = 0; j < n; j++) {
			char call[11];
			scanf("%s", call);
			if (tree->insert(call) == false) {
				f = false;
			}
		}
		if (f)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}