[BOJ 5670] 휴대폰 자판

 

[문제]

 

www.acmicpc.net/problem/5670

5670번: 휴대폰 자판

 

[난이도] 

 

- Platinum III (solved.ac 20.12.13 기준)

 

 

[필요 개념]

 

- 트라이 (Trie)

 

 

[풀이]

 

자동 입력이 되는 순간은 현재 노드에서 끝나는 문자열이 없으면서, 자식 노드가 하나밖에 없는 경우이다.

따라서 트라이를 생성할 때 자식의 수를 저장해두고, 문자열을 탐색할 때 자식의 수가 둘 이상이거나,

현재 노드에서 끝나는 다른 문자열이 있고 자식의 수가 1이면 버튼을 눌러줘야 하기 때문에 +1을 해서 다음 노드로 넘겨준다.

문자열의 끝에 도달하면 지금까지 더해온 값을 ans에 추가해준다.  

 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int ans;
struct Trie {
	Trie *ch[26];
	int cnt;
	bool end;
	Trie() {
		for (int i = 0; i < 26; i++) ch[i] = NULL;
		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) {
			ans += k;
			return;
		}
		int now = *s - 'a';
		if (root) ch[now]->find(s + 1, k, false);
		else {
			if (cnt == 1 && !end) ch[now]->find(s + 1, k, false);
			else ch[now]->find(s + 1, k + 1, false);
		}
	}
};
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n;
	while (cin>>n) {
		Trie *root = new Trie;
		ans = 0;
		vector<string> v;
		for (int i = 1; i <= n; i++) {
			string s; cin >> s;
			v.push_back(s);
			root->insert(s.c_str());
		}

		for (string s : v) {
			root->find(s.c_str(), 1, true);
		}
		cout << fixed;
		cout.precision(2);
		cout << (double)ans / sz(v) << '\n';
		delete root;
	}
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^