[백준] 5670번 휴대폰 자판

링크

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

5670번: 휴대폰 자판

풀이

각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 문제이다.

 

입력받은 각 단어들을 트라이를 이용하여 트리를 만들어 주었는데

이때 alpa_cnt라는 현재 트리 노드의 위치에서 내가 가진 자식들의 개수를 세어주는 변수를 하나 만들었습니다.

 

root 노드에서는 h 와 g 자식을 가지고 있기 때문에 alpa_cnt 가 2가 되고 

 

h 노드에는 자식이 e 한개 밖에 없으므로 alpa_cnt -> 1

 

e 노드에는 a와 l 자식을 가지기 때문에 alpa_cnt -> 2

 

이렇게 현재 노드 위치에서 자식의 개수를 세어 주도록 했습니다.

 

그리고 find 함수를 통하여 탐색을 시작하는데 

 

단어 탐색을 시작 할때는 자동으로 입력이 안되기 때문에 무조건 시작 알파벳을 한번 눌러줘야 합니다

그 이후에 자식이 2개 이상 가지고 있을 때 역시 자동으로 입력이 안되기 때문에 알파벳을 한번 눌러주어야 합니다.

 

그리고 hell는 h에서 한번, e에서 한번 이렇게 2번을 입력하면 되지만

hello 같은 경우에는 h에서 한번, e에서 한번 마지막으로 l에서 한번 총 3번을 입력해야 합니다.

 

hello와 같은 단어 속에 단어가 있는 경우를 확인하기 위해

내가 가지고 있는 자식(alpa_cnt)이 1개이지만 is_finish가 true인지 확인하고 is_finish가 true이면 한 번 더 눌러 주어야 됩니다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 30
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

struct Trie {
	Trie *node[SIZE];
	int alpa_cnt;
	bool is_finish, is_child;

	Trie() {
		fill(node, node + SIZE, nullptr);
		alpa_cnt = 0; is_finish = is_child = false;
	}

	~Trie() {
		for (int i = 0; i < SIZE; i++) {
			if (node[i])
				delete node[i];
		}
	}

	void insert(const string &word, int index) {
		if (index >= word.size()) {
			is_finish = true;
			return;
		}
		else if (index < word.size()) {
			int word_index = word[index] - 'a';
			if (node[word_index] == NULL) {
				alpa_cnt++;
				is_child = true;
				node[word_index] = new Trie();
			}

			node[word_index]->insert(word, index + 1);
		}
	}

	int find(const string &word, int index, int cnt) {
		if (index >= word.size()) {
			return cnt;
		}
		int res = 0;
		int word_index = word[index] - 'a';

		if (index != 0 && (alpa_cnt != 1 || (alpa_cnt == 1 && is_finish == true)) && node[word_index] != NULL) {
			res = node[word_index]->find(word, index + 1, cnt + 1);
		}
		else {
			res = node[word_index]->find(word, index + 1, cnt);
		}

		return res;
	}
};
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	while (1) {
		int N; cin >> N;
		if (cin.eof() == true)
			break;
		Trie root; vector<string> words;
		for (int i = 0; i < N; i++) {
			string word; cin >> word; words.push_back(word);
			root.insert(word, 0);
		}

		double res = 0;
		for (auto word : words) {
			res += root.find(word, 0, 0) + 1;
		}

		cout << fixed;
		cout.precision(2);
		cout << res / double(N) << "\n";
	}
}