[BOJ/C++] 5670(휴대폰 자판)

1. Link

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

2. 풀이 과정

1. 읽으면 바로 트라이 문제라는 것을 파악 가능해서 유형파악은 생략 -> Trie
2. 각 철자마다 지나가며 만약 중복되지 않으면 자동 입력으로 쳐서 세지 않고, 이외의 경우 세는 것으로 각 횟수의 평균을 구해야함

• 테스트 케이스의 제한이 없어 입력이 끝날 때 까지 받아야 합니다. 이를 위해 while(cin >> n)으로 while문에서 입력이 들어올 때 이후 과정을 진행할 수 있도록 구현했습니다.
• 소수점 조건을 만족시키기 위해 iomanip 헤더를 사용하였습니다. 아래의 코드와 같이 fixed 및 setprecision을 통해 원하는 자릿수를 설정하는 것으로 조건을 충족시킵니다.
  cout << fixed << setprecision(x) << value

3. 정답 코드

#include<iostream>
#include<vector>
#include<map>
#include<iomanip>
using namespace std;

struct Trie {
private
:	bool isEnd = false;
	map<char, Trie*> child;
public:
	void insert(string s, int idx) {
		if (s.length() == idx) {
			this->isEnd = true;
			return;
		}
		if (child[s[idx]] == nullptr) {
			child[s[idx]] = new Trie();
		}
		child[s[idx]]->insert(s, idx + 1);
	}
	int countAuto(string s) {
		int cnt = 1;
		Trie* t = child[s[0]];
		for (int i = 1; i < s.length(); ++i) {
			if (t->child.size() > 1 || t->isEnd == true) {
				++cnt;
			}
			t = t->child[s[i]];
		}
		return cnt;
	}
};

double solution(int n) {
	vector<string> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	Trie* root = new Trie();
	for (auto s : v) {
		root->insert(s, 0);
	}
	int sum = 0;
	for (auto s : v) {
		sum += root->countAuto(s);
	}
	double answer = (double)sum / n;
	return answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	while (cin >> t) {
		cout << fixed << setprecision(2) << solution(t) << '\n';
	}
	return 0;
}