5670 - 휴대폰 자판 (Trie, 정적 풀이)

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

5670번: 휴대폰 자판

대놓고 트라이 써라는 문제입니다.

 

원래는 동적으로 필요할 때마다 만들어서 문제를 풀려고 했다가, 어차피 프로 시험에서 정적으로 문제 풀거 정적으로 풀어봐야겠다해서 정적으로 풀었습니다.

 

음...

 

다시 생각해보니 동적으로도 풀어봐야할거 같네요. 과연 시간 초과가 날지 궁금하니까요.

우선 정적으로 푼 코드를 살펴보기 전에, 알고리즘부터 타고 들어가봅시다.

 

문제는 읽어보시면 아실거고, 저희는 각 단어마다 언제 카운트를 해야하는지가 중요합니다.

 

만약 아래의 단어가 있다고 가정을 해봅시다.

발퀄 ㅈㅅ..

 

딱 봐도 아시겠죠? 트라이인거, 파란색 동그라미 쳐진 곳이 endOfWord라고 단어의 끝입니다.

 

즉, hi / hee / heeo / heeoy / heeoi 라는 단어들이 존재한다는 뜻입니다. (무슨 뜻인진 저도 모릅니다)

 

그렇다면 언제 카운트를 해줘야 할까요?

 

1. 맨 처음 => 맨 처음 단어가 어떻게 시작하는 지 알아야 가지를 펼칠 수 있겠죠.

2. n + 1 단어의 가지 수가 2개 이상일 때 => 2개 이상일 땐 어느 가지로 나아가야하는지 알아야 하니까 추가 입력이 필요합니다.

3. 한 단어가 endOfWord를 지나칠 때 => 위에서 보다시피 heeoy라는 단어로 가기 위해선 hee / heeo 라는 단어를 거치고 지나가야합니다. 따라서 추가적인 카운트를 그 때마다 해줘야 구분이 됩니다.

 

여기까지 분기하면 문제는 풀립니다.

 

Trie 알고리즘 설명은 다른 곳에서 많이 했으니 ㅎㅎ.. 제가 올려놓은 다른 곳에서 찾을 수 있으실 것입니다. ㅎㅅㅎ

https://ggodong.tistory.com/160

5052 - 전화번호 목록

#include <stdio.h>
#include <string.h>

#define MAX_TRIE_LEN 1000000
#define ALPHABET 26

int trie[MAX_TRIE_LEN][ALPHABET];
int count[MAX_TRIE_LEN];
int endOfWord[MAX_TRIE_LEN];
int adr;

void initTrie() {
	adr = 0;
	memset(trie, 0, sizeof(trie));
	memset(count, 0, sizeof(count));
	memset(endOfWord, 0, sizeof(endOfWord));
}

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] = ++adr;
			++count[cur];
		}
		cur = trie[cur][num];
		idx++;
	}
	endOfWord[cur] = 1;
}

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

int N;
char words[100000][81];
double res;

int main(void) {
	while (scanf("%d", &N) != EOF) {
		initTrie();
		res = 0;
		for (int n = 0; n < N; n++) {
			scanf("%s", words[n]);
			insert(words[n]);
		}
		for (int n = 0; n < N; n++) {
			res += find(words[n]);
		}
		res /= N;
		printf("%.2lf\n", res);
	}
	return 0;
}

 

 

사실 이 문제를 풀 때 제가 직면한 것은 알고리즘이 아니었습니다. (시도 횟수에서 아시겠죠)

 

아까 동적으로 풀려다가 정적으로 풀었다고 했는데, 아마 프로 문제에서 이 문제가 나왔다면 저는 통과할 수 없었을 것입니다.

 

그 이유는 initTrie()라는 함수 안에 있는데, 이 문제는 새로운 케이스가 들어올 때마다 새로 초기화를 해야하는 전역 변수 때문에 중간에 시간초과가 뜨게 되었습니다.

 

처음엔 for문으로 순회를 하면서 초기화를 하려했다가 도저히 시간을 뚫지 못했고, for 문보다 빠른게 memset 함수임을 알고 이를 사용해서 문제를 해결했습니다.

 

그게 좀 억울해서 동적으로 문제를 풀어야겠다 !!!!!!... 까지만 생각하고 밤이 너무 늦어 자려고 합니다.

---

이상 5670 - 휴대폰 자판 (Trie)였습니다. ^_^