[BOJ] 5670 휴대폰 자판

vector로 트라이 구현하기

Table Of Contents

0. 들어가기

1. 문제 요약

사전에 저장된 영단어의 갯수와 해당 갯수대로 영단어 목록이 주어진다.

단어를 입력할 때, 가능한 다음 글자가 하나 뿐이라면 자동으로 다음 글자가 입력된다.

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

2. 풀이 정리

모든 단어를 트라이에 저장한다.

트라이의 루트 노드에서부터 시작해서 모든 노드를 탐색한다.

3. 구현

트라이의 각 노드는 bool isEnd, vector<pair<char, node*> > next를 가진다.

전체 코드

#include <iostream>
#include <vector>
#include <string>
#define endl '\n'
#define nodePair pair<char, node*>
using namespace std;

int N;
int totalCnt;

struct node {
	bool isEnd;
	vector<nodePair> next;

	node()
	{
		isEnd = false;
	}

	void insert(string S, int index)
	{
		if (index == S.length())
		{
			isEnd = true;
			return;
		}

		char nextChar = S[index];
		node* nextPtr = NULL;

		for (nodePair nextNode : next)
		{
			if (nextNode.first == nextChar)
				nextPtr = nextNode.second;
		}

		if (nextPtr == NULL)
		{
			nextPtr = new node;;
			next.push_back({ nextChar, nextPtr });
		}
		nextPtr->insert(S, index + 1);
	}

	void find(int cnt)
	{
		int nextCnt = 0;

		if (isEnd)
		{
			nextCnt++;
			totalCnt += cnt;
		}

		for (nodePair nextNode : next)
		{
			if (nextNode.second)
				nextCnt++;
		}

		if (cnt && nextCnt == 1)
		{
			for (nodePair nextNode : next)
			{
				if (nextNode.second)
					nextNode.second->find(cnt);
			}

		}
		else
		{
			for (nodePair nextNode : next)
			{
				if (nextNode.second)
					nextNode.second->find(cnt + 1);
			}
		}
	}
};

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (cin >> N)
	{
		node root;
		totalCnt = 0;

		for (int i = 0; i < N; i++)
		{
			string S;
			cin >> S;
			root.insert(S, 0);
		}

		root.find(0);

		cout << fixed;
		cout.precision(2);
		cout << totalCnt / (double)N << endl;
	}

	return 0;
}

4. 여담