[Algorithm][C++] BOJ 5670: 휴대폰 자판 (Trie)

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

5670번: 휴대폰 자판

 

풀이 핵심

1. Trie 자료구조를 활용한다. 

 

2. Trie root에 문자열을 insert 할 때 문자 ('a' ~ 'z') 가 나온 수를 각 문자마다 체크 한다.

ex) "hello", "hell"

- "hello" insert하고 난 뒤

- "hell" insert하고 난 뒤

3. search 할 때 post_cnt와 비교하면서 버튼 누를 횟 수를 증가 시킨다. (post_cnt와 다음 Trie cnt가 다르면 버튼 누를 횟수 1 증가)

ex) "hello", "hell"

"hello", "hell" insert하고 난 뒤 "hello" search

* 처음 post_cnt는 0으로 한다, post_cnt와 현재 Trie의 다음 문자의 cnt를 비교해야 한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>

int N, sum;
char content[100001][81];

int cnum[512];

struct Trie {
	int cnt;
	Trie* next[26];

	Trie():cnt(0){
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (register int i = 0; i < 26; ++i)
			if (next[i]) delete next[i];
	}

	void insert(const char* str) {
		if (*str == '\0') return;

		if (next[cnum[*str]] == 0) {
			next[cnum[*str]] = new Trie();
		}
		++next[cnum[*str]]->cnt;

		next[cnum[*str]]->insert(str + 1);
	}

	void search(const char* str, int post_cnt) {
		if (*str == '\0') return;

		if (post_cnt != next[cnum[*str]]->cnt) ++sum;

		next[cnum[*str]]->search(str + 1, next[cnum[*str]]->cnt);
	}
} *root;

int main() {
	for (register int c = 'a'; c <= 'z'; ++c) cnum[c] = c - 'a';
	while (scanf("%d", &N) != EOF) {
		register int i;
		root = new Trie();
		for (i = 0; i < N; ++i) {
			scanf("%s", content[i]);
			root->insert(content[i]);
		}

		sum = 0;

		for (i = 0; i < N; ++i) root->search(content[i], 0);
		printf("%.2f\n", (float)sum / N);

		delete root;
	}
	return 0;
}