[Baekjoon,5670] 휴대폰 자판

각 단어들을 트라이로 구현하여 해결하면 된다. 이때 타이핑을 해야하는 순간을 잘 생각해야 한다. 그 시점은 아래와 같다.

1. 문장의 첫 글자를 타이핑하는 경우
2. 현재 형성된 문장에서 문자 갈림길이 존재하는 경우
3. 현재 문장이 완성본과 같은데 추가로 단어가 존재하는 경우

이를 그림으로 표현하면 아래와 같다. 1번은 주황색, 2번은 녹색, 3번은 하늘색으로 표현하였다.

구현

이와 같은 과정을 코드로 구현하면 아래와 같다. 트리 구조의 각 자식을 $map$을 이용하여 저장하고 있으며 이를 이용하여 자식이 두 개 이상이면 타이핑을 하고 있다. 또한 따로 $terminal$ 변수를 이용하여 현재 노드에서 문자가 완성되는 지 확인할 수 있다. 이를 통해 위 그림의 하늘색 부분을 처리할 수 있다. 주의할 점은 루트에서 자식이 2개 이상인 경우를 추가로 카운트 하지 않아야 하는 것이다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;

struct TrieNode
{
	map<char, TrieNode*> children;
	bool terminal;
	TrieNode() : terminal(false) {}
	// 트라이에 문자열 key 삽입
	void insert(const char* key)
	{
		if (*key == 0)
			terminal = true;
		else
		{
			// 노드가 없는 경우 생성
			if (children.count(*key) == 0)
				children[*key] = new TrieNode();
			children[*key]->insert(key + 1);
		}
	}
	int needed_typing(const char* key)
	{
		if (*key == 0) return 0;
		int typing = 0;
		// 문자가 2개로 갈리거나 현재 문자로 끝나는 단어가 있을 경우 
		if (children.size()>1 || terminal)
			++typing;
		return typing + children[*key]->needed_typing(key + 1);
	}
};

int main()
{
	int n;
	while (scanf("%d", &n) != EOF)
	{
		vector<string> words;
		TrieNode* trie = new TrieNode();
		for (int i = 0;i < n;++i)
		{
			char str[82];
			scanf("%s", str);
			// 끝에 한 글자 추가
			string s = str;
			//cout<<s<<endl;
			words.push_back(s);
			trie->insert(str);
		}

		int ret = 0;
		for (int i = 0;i < n;++i)
			// 해당 단어의 시작 문자에서 바로 시작 
			ret += 1 + trie->children[words[i][0]]->needed_typing(words[i].c_str() + 1);

		printf("%.2f \n", (double)ret / n);
		//cout << ret << endl << endl;
	}
	return 0;
}