BOJ : 5670 휴대폰 자판

---

[BOJ 5670(P3)리뷰]

저장된 단어를 기준으로 자판 자동완성(?) 기능을 만들어야 한다.
예를들어, hello라는 단어가 저장되어 있다면 he만 입력해도 hello라는 단어가 완성되어야 한다.
하지만 h로 시작하는 단어가 2개 이상이라면 자동완성이 되어서는 안되고 사용자로부터 입력을 받아야 한다.

즉, 단어 사전에 hello 와 heaven만 저장되어 있다면 h를 누르는 순간 'e'가 자동으로 입력되어야 하고 (h로 시작하는 단어는 모두 뒤에 e가 붙으므로) 그 후에는 사용자로부터 입력을 받아야 한다.

그리고 만약 he가 입력된 상태에서 'l'을 입력하게 되면 그 후에는 존재하는 단어가 1개이므로 'hello'까지 자동완성 되어야 한다.

입력으로 휴대폰에 저장된 단어의 목록이 주어졌을 때, 각각의 단어들을 완성시키기 위하여 사용자로부터 입력을 총 몇번받았는지 세어 평균을 구해야 하는 문제이다.

단어의 갯수가 최대 10만개까지 주어지므로 단어 하나 하나 다른 단어들과 비교해보는것은 1초내에 풀 수 없다.
그렇기에 트라이 라는 자료구조를 이용하여 문제를 해결했다.

1. 주어진 단어들을 insert한다. 이 때 각각의 노드마다 child의 갯수를 기록한다.
2. 모든 단어에 대해 insert가 끝난 후 각각의 단어들의 자판누르는 과정을 시뮬레이션 한다.
3. 만약 현재노드의 child가 1개라면 다음에 입력할 수 있는 자판은 유일하므로 카운팅하지 않는다.
4. 단어의 끝까지 도달했을 때 최종적으로 카운팅 된 값이 사용자로부터 입력을 받은 횟수이다.

/*
	21.01.15
	BOJ : 5670 휴대폰 자판 (https://www.acmicpc.net/problem/5670)
	자료구조/트라이
*/
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	Node* child[26];
	bool isEnd;
	int childCount;

	Node() { 
		memset(child, NULL, sizeof(child)); 
		isEnd = false;
		childCount = 0;
	}

};

void insert(string word,Node *root) {
	Node* current = root;

	int len = word.size();
	for (int i = 0; i < len; i++) {
		int nxt = word[i] - 'a';
		if (current->child[nxt] == NULL) {
			current->child[nxt] = new Node;
			current->childCount += 1;
		}
		current = current->child[nxt];
	}

	current->isEnd = true;
}

int query(string word,Node *root) {
	Node* current = root->child[word[0] - 'a'];
	int ret = 1;
	int len = word.size();
	for (int i = 1; i < len; i++) {
		int nxt = word[i] - 'a';

		if (current->childCount == 1 && current->isEnd == false) { //갈 수 있는 단어가 1개만 존재
			current = current->child[nxt];
		}
		else {
			current = current->child[nxt];
			ret++;
		}
	}

	return ret;
}

void clear(Node* cur) {
	for (int i = 0; i < 26; i++) {
		if (cur->child[i] != NULL) {
			clear(cur->child[i]);
		}
	}

	delete cur;
}

vector <string> words;


int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(0);
	Node root;
	while (true) {
		int N;
		cin >> N;
		if (cin.eof()) break;
	
		Node* root = new Node;
		for (int i = 0; i < N; i++) {
			string temp;
			cin >> temp;
			words.push_back(temp);
		}
	
		//단어 INSERT
		for (string& v : words) {
			insert(v,root);
		}

		int cnt = 0;
		for (string& v : words) {
			cnt += query(v,root);
		}

		printf("%.2f\n", (float)cnt / N);
		
		words.clear();
		clear(root);
	}

	return 0;
}