14425 - 문자열 집합 (Trie 풀이)

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

14425번: 문자열 집합

Trie를 더 연습해봅시다 !!

 

문제는 뭐 이해가 안가실건 없다고 생각합니다. 라이브러리를 쓰면 간단하게 풀 수 있는 문제인데.. 저희는 프로를 위한 준비로 구현 능력을 직접!! 기르는 시간을 가져보도록 합시다.

 

이 후 Hash로도 한 번 더 풀어볼게요 ㅎㅅㅎ

 

제가 짠 Trie는 이렇습니다.

#include <stdio.h>
#include <malloc.h>

typedef struct _node {
	struct _node* alp[30];
	int tnf;
} Node;

Node* Trie, * root,* tmp, * node;

int N, M, idx, num, result = 0;
char word[505];

Node* makeNode() {
	node = (Node*)malloc(sizeof(Node));
	for (int i = 0; i < 30; i++) {
		node->alp[i] = NULL;
	}
	node->tnf = 0;
	return node;
}

void insert(char* word) {
	idx = 0;
	root = Trie;
	while (word[idx] != '\0') {
		tmp = makeNode();
		num = (int)word[idx] - 'a';
		if (root->alp[num]) {
			root = root->alp[num];
			idx++;
			continue;
		}
		root->alp[num] = tmp;
		root = root->alp[num];
		idx++;
	}
	root->tnf = 1;
}

int find(char* word) {
	idx = 0;
	root = Trie;
	while (word[idx] != '\0') {
		num = (int)word[idx] - 'a';
		if (root->alp[num]) {
			root = root->alp[num];
			if (root->tnf && word[idx + 1] == '\0') return 1;
		}
		else return 0;
		idx++;
	}
	return 0;

}

int main(void) {
	Trie = makeNode();
	scanf("%d %d", &N, &M);
	// N
	for (int n = 0; n < N; n++) {
		scanf("%s", word);
		insert(word);
	}
	// M
	for (int m = 0; m < M; m++) {
		scanf("%s", word);
		if (find(word)) {
			result++;
		}
	}
	printf("%d", result);
}

보시다시피 새로운 글자가 들어올 때 마다 저는 makeNode() 함수로 node를 동적으로 생성하며 알고리즘을 구성했는데, 매우 느렸습니다.

메모리도 엄청 많이 쓴거 같은데 ㄷㄷ;;

그래서 한 번 정적으로 풀 수 없을까도 고민을 해보았습니다.

 

결국 저희가 궁금한거는 이거입니다. root 노드에서 이어진 주소값이 있는지와 그 노드가 단어의 마지막을 가리키는지 아닌지를 확인하면 됩니다.

 

그렇다면 주소값은 항상 고유의 숫자로 가지게 만들면 되겠죠. 즉, 그 주소값을 가리키는 것은 하나만 존재한다는 것입니다.

 

여기까지는 됐다 치고, 제가 가장 궁금했던건 바로 범위였는데요.

 

이 문제에서는 500자의 10000개 단어가 최대 범위로 잡혀있습니다. 이런 경우엔 범위를 어떻게 잡는게 좋을까요? 우선 a에서 b로 가는 값과 c에서 b로 가는 값은 달라야하기에 범위를 단지 최대 문자 길이(500자)로 잡기에는 무리가 있습니다. (제가 처음에 이렇게 했었습니다. Trie[500][26])

 

한 번 최악의 경우를 생각해봅시다. 500자의 10000개 단어가 존재한다면, 최악의 경우엔 모든 글자의 주소값을 알아야합니다. 물론 알파벳이 26자가 끝이기에 이런 경우가 있냐 싶다만은, 최약의 경우엔 500*10000개의 주소값이 필요합니다.

 

즉, endOfWord 배열의 범위가 500 * 10000개가 될 수 있단 얘기입니다. (최악의 경우엔 500*10000개의 주소값이 존재하며, 그 주소값이 단어의 끝인지 아닌지를 알아야하니까요)

 

그렇다면 Trie배열의 경우엔 어떨까요? 우선 26개의 배열이 존재해야한다는건 직감적으로 알 수 있습니다. 또한, endOfWord 배열과 마찬가지로 500 * 10000개의 배열이 2차원으로 존재해야합니다. 각 주소값마다 26개의 알파벳 가지 수가 존재해야하니까요.

 

사실 바로 이해하기 힘든 부분이다보니 코드를 살펴봅시다.

#include <stdio.h>

int N, M, result = 0, trie[10000 * 505][30], add = 0, endOfWord[10000 * 505];
char word[502];

void insert(char* word) {
	int idx = 0, num, cur = 0;
	while (word[idx] != '\0') {
		num = (int)word[idx] - 'a';
		if (!trie[cur][num]) trie[cur][num] = ++add;
		cur = trie[cur][num]; idx++;
	}
	endOfWord[cur] = 1;
}

int find(char* word) {
	int idx = 0, num, cur = 0;
	while (word[idx] != '\0') {
		num = (int)word[idx] - 'a';
		if (!trie[cur][num]) return 0;
		cur = trie[cur][num]; idx++;
	}
	if (endOfWord[cur]) return 1;
	else return 0;
}

int main(void) {
	scanf("%d %d", &N, &M);
	// N
	for (int n = 0; n < N; n++) {
		scanf("%s", word);
		insert(word);
	}
	// M
	for (int m = 0; m < M; m++) {
		scanf("%s", word);
		if (find(word)) result++;
	}
	printf("%d", result);
}

확실히 간단해졌죠? add가 주소값을 만들어주며, trie, endOfWord의 배열이 주소값을 포함하면서 각 단어의 상태를 저장하고 있습니다. 또한, 함수 중간마다 cur의 변수가 현재 어떤 노드를 가리키는지를 파악해주면서 앞서 보인 코드보다 훨씬 간단하게 문제를 해결할 수 있었습니다.

사실 동적으로 문제를 푸는게 직관적이라 좋아하는 편인데, 시간 차이가 2배 정도까지 날 지는 저도 몰랐습니다.

 

프로 시험 준비하려면 정적으로 범위를 생각하면서 문제를 풀어야 할거 같네요.

 

이 문제를 해시로 한 번 더 풀어보겠습니다.

---

이상 14425 - 문자열 집합 (Trie 풀이) 였습니다. ^_^