BOJ 5670 - 새로운 자판 (Trie)

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

이정도까진 풀수 있어야 한다.

 

<문제설명>

자동완성 기능이 있는 자판이 있다. abczx abcxx abcyy 가 등록되어 있다고 가정할 때, a를 자판에 누르는 순간 abc가 자동완성된다. 등록되어있는 단어들을 모두 입력하는데 자판을 누르는 회수의 총합을 전체 등록된 문자의 수로 나눈 것을 구하자.

 

<풀이>

예제를 그린것

등록된 문자를 모두 find하면서 각 문자를 쓰는데 눌러야하는 자판 횟수를 ll cntKey(char* key, bool isRoot, ll cnt) 라고 하자.

 

main에서 호출, 출력하는 코드

ll sum = 0;
for (int i = 0; i < n; i++)
	sum += root->cntKey(w[i], 1, 0);
printf("%.2lf\n", 1.0 * sum / n);

 

cnt를 더하는 경우는

1) 현재 노드가 루트인 경우

2) 현재 노드의 자식(branch)이 두개 이상인 경우 -> insert때 만들어준다.

3) 현재 노드가 term==true인 경우

 

위의 조건에 맞게 find를 잘 구현해주면 된다.

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

struct Trie {
	Trie* next[26];
	bool term;
	int branch; //자식 수

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

	void insert(char* key) {
		if (*key == NULL) {
			term = true;
			return;
		}
		int c = *key - 'a';
		if (next[c] == NULL) {
			branch++;
			next[c] = new Trie();
		}
		//words++; //여길 거쳐가는 횟수만큼 후손이 있는 것
		next[c]->insert(key + 1);
	}

	ll cntKey(char* key, bool isRoot, ll cnt) {
		if (*key == NULL) {
			return cnt;
		}
		ll rst = 0;
		if (isRoot || branch > 1) rst = 1;
		if (branch == 1 && term) rst = 1;

		int c = *key - 'a';
		return next[c]->cntKey(key + 1, 0, cnt + rst);
	}
};

int main() {
	int n;
	while (scanf("%d", &n) > 0) {
		Trie* root = new Trie();
		char w[100005][81];
		for (int i = 0; i < n; i++) {
			cin >> w[i];
			root->insert(w[i]);
		}
		ll sum = 0;
		for (int i = 0; i < n; i++)
			sum += root->cntKey(w[i], 1, 0);
		printf("%.2lf\n", 1.0 * sum / n);
		delete root;
	}
}

 

<생각>

dp와 연계되서 나올 가능성도 있는 것 같다..ㅠ