[Algorithm][C++] BOJ 5052: 전화번호 목록 (Trie)

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

5052번: 전화번호 목록

 

풀이 핵심

1. 문자열 처리 문제로 접두어를 이용해 자료구조를 만들어야 하므로  Trie 자료구조 사용

2. Trie에 번호들을 저장, 탐색하고 문자열이 끝나기 전 isTerminal이 true일 경우 접두어가 존재하는 것이므로 false를 반환한다.

 

코드

#include <cstdio>
#include <cstring>
#define MAX_N	10000
#define MAX_L	11

int charToInt(char c) { return c - '0'; }

int tCnt;

struct Trie {
	bool isTerminal;
	Trie* next[MAX_L];

	void init() {
		isTerminal = false;
		memset(next, 0, sizeof(next));
	}
}tries[MAX_N * MAX_L];

#define allocTrie (&tries[tCnt++])

bool insert(Trie* cur, const char* key) {
	if (*key == '\0') {
		cur->isTerminal = true;
		return true;
	}
	else {
		if (cur->isTerminal == true) return false;

		int index = charToInt(*key);

		if (cur->next[index] == 0) {
			cur->next[index] = allocTrie;
			cur->next[index]->init();
		}
		else if (*(key + 1) == '\0') return false;

		return insert(cur->next[index], key + 1);
	}
}

int main() {
	char tmp[MAX_L];
	int T;
	scanf("%d", &T);
	while (T--) {
		tCnt = 0;
		int n;
		scanf("%d", &n);
		
		Trie* root = &tries[tCnt++];
		root->init();

		bool ret = true;

		for (int i = 0; i < n; ++i) {
			scanf("%s", tmp);

			if (ret == false) continue;

			ret = insert(root, tmp);
		}

		printf("%s\n", ret ? "YES" : "NO");
	}
	return 0;
}