[백준/BOJ] 백준 5670번 : 휴대폰 자판

www.acmicpc.net/problem/5670

5670번: 휴대폰 자판

트라이를 이용하여 문제를 해결했다. 트라이 구조를 만들고, 각 단어마다 버튼을 누르는 개수를 셀 때, 트라이 구조를 만들 때 저장한 children_num을 이용한다. children_num이 1일때 해당 위치에서 끝나는 단어가 저장되어 있지 않다면 다음 글자로 자동 입력할 수 있다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

//트라이 알고리즘을 이용한다
//알고리즘 문제해결 전략2 책 트라이 알고리즘 공부 실습

int n;
struct node {
	node* children[26];
	int children_num;
	int finish;
};

void Pre_node(node* maked_node)
{
	for (int i = 0; i < 26; i++)
		maked_node->children[i] = NULL;

	maked_node->children_num = 0;

	maked_node->finish = 0;
}

void Delete_node(node* tree)
{
	if (tree == NULL)
		return;

	for (int i = 0; i < 26; i++)
	{
		if (tree->children[i] != NULL)
			Delete_node(tree->children[i]);
	}

	delete tree;
}

void Insert(node* tree, string& input, int index)
{
	if (index == input.size())
	{
		tree->finish = 1;
		return;
	}

	if (tree->children[input[index] - 'a'] == NULL)
	{
		node* maked_node = new node();
		Pre_node(maked_node);

		tree->children[input[index] - 'a'] = maked_node;
		tree->children_num++;
	}

	Insert(tree->children[input[index] - 'a'], input, index + 1);
}



int Count(node* tree, string& input, int index)
{
	int ret = 0;

	if (index == input.size())
		return 0;

	//children이 하나일때
	if (tree->children_num == 1)
	{
		if (index == 0) //첫 글자 일때는 무조건 눌러야 된다
			ret = Count(tree->children[input[index] - 'a'], input, index + 1) + 1;
		else if (tree->finish == 0) //자동입력
			ret = Count(tree->children[input[index] - 'a'], input, index + 1);
		else if (tree->finish == 1) //해당 구간에서 끝나는게 있을때
			ret = Count(tree->children[input[index] - 'a'], input, index + 1) + 1;
	}

	else
		ret = Count(tree->children[input[index] - 'a'], input, index + 1) + 1;

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	double result = 0;
	node* root;
	vector<string> input_list;

	while (cin >> n)
	{
		root = new node();

		for (int i = 0; i < n; i++)
		{
			string input;

			cin >> input;
			input_list.push_back(input);

			Insert(root, input, 0);
		}

		int input_list_size = input_list.size();

		for (int i = 0; i < input_list_size; i++)
		{
			result += (double)(Count(root, input_list[i], 0));
		}
		result /= n;

		cout << fixed;
		cout.precision(2);
		cout << result << "\n";

		Delete_node(root);
		input_list.clear();
		result = 0;
	}

	return 0;
}