BOJ 5670 휴대폰 자판

1 개요

BOJ 5670 휴대폰 자판

• 백준 온라인 저지 5670번 문제
• BOJ 41단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N;
double answer;

struct Trie {
	Trie *ch[26];
	int cnt;
	bool end;
	Trie() {
		for (int i=0; i<26; i++) {
		    ch[i] = 0;
		}
		cnt = 0;
		end = false;
	}
	~Trie() {
		for (int i=0; i<26; i++) {
		    if (ch[i]) delete ch[i];
		}
	}
	void insert(const char* s) {
		if (!*s) {
			end = true;
			return;
		}
		int now = *s - 'a';
		if (!ch[now]) {
			ch[now] = new Trie;
			cnt++;
		}
		ch[now]->insert(s+1);
	}
	void find(const char *s, int k, bool root) {
		if (!*s) {
			answer += k;
			return;
		}
		int now = *s - 'a';
		if (root) {
		    ch[now]->find(s+1, k, false);
		    return;
		}
		if (cnt == 1 && !end) {
		    ch[now]->find(s+1, k, false);
		} else {
		    ch[now]->find(s+1, k+1, false);
		}
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed;
	cout.precision(2);
	while(cin >> N) {
	    answer = 0;
		vector<string> v;
		string temp;
		Trie *root = new Trie;
		for (int i=0; i<N; i++) {
			cin >> temp;
			v.push_back(temp);
			root->insert(temp.c_str());
		}
		for (const auto& s: v) {
			root->find(s.c_str(), 1, true);
		}
		delete root;
		cout << answer/v.size() << '\n';
	}
}