[백준] 5670번 - 휴대폰 자판

문제

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

 

풀이

Trie: https://doraeul19.tistory.com/415

전형적인 트라이 문제, 근데 입출력 형식이 여러개의 TC이므로 while(cin >> N)으로 입력받자

Insert함수를 구현해서 트리를 잘 만들어주고, Find함수에서 자판을 눌러야하는 횟수를 더해가면 된다.

 

자판을 눌러야 하는 경우

1. 맨 처음 글자: 첫 번째 글자는 무조건 눌러야 한다.

2. 다른 문자열과 구분되지 않는 경우

    - 현재 문자가 isEnd(다른 문자열의 끝인 경우)

    - 다음 문자로 올 수 있는 경우가 2개 이상인 경우

 

코드

#include <vector>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <unordered_map>
#include <map>
#include <cmath>
using namespace std;
int T;
int N;
string arr[100000];
double s = 0;
struct Trie {
	int isEnd;
	Trie* child[26];
	int childCnt;
	Trie() {
		isEnd = 0;
		childCnt = 0;
		for (int i = 0; i < 26; ++i) child[i] = NULL;
	}
	~Trie() {
		for (int i = 0; i < 26; ++i) delete child[i];
	}

	void Insert(string& str, int index)
	{
		if (index == str.size()) {
			isEnd = 1;
			return;
		}
		int ch = str[index] - 'a';
		if (child[ch] == NULL) {
			childCnt++;
			child[ch] = new Trie();
		}
		child[ch]->Insert(str, index + 1);
	}

	int Find(string& str, int index, int cnt)
	{
		if (index == str.size()) {
			s += cnt;
			return isEnd;
		}
		int ch = str[index] - 'a';
		if (child[ch] == NULL) return 0;
		else {
			if (index == 0 || isEnd || childCnt > 1) return child[ch]->Find(str, index + 1, cnt + 1);
			else return child[ch]->Find(str, index + 1, cnt);
		}
	}
};
void solve()
{
	Trie root;
	string inp;
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
		root.Insert(arr[i], 0);
	}
	s = (double)0.0;
	for (int i = 0; i < N; ++i) {
		root.Find(arr[i], 0, 0);
	}
	double ret = round((s / (double)N) * 100.0) / 100.0;
	cout << ret <<"\n";
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout.precision(2);
	cout << fixed;
	while (cin >> N) solve();
	return 0;
}