[백준/BOJ] 백준 16934번 : 게임 닉네임

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

16934번: 게임 닉네임

트라이 자료구조를 이용해서 문제를 해결했다. 노드에는 해당 노드에서 끝나는 문자열의 개수, 해당 노드에서 나아가는 알파벳별 개수를 저장하여 확인을 할 때 해당 노드에서 끝나는 문자열의 개수를 통해 같은 닉네임으로 가입한 사람의 수를 계산하거나, 알파벳별 개수를 통해 해당 접두사가 이전에 가입한 닉네임의 접두사와 겹치지 않을 때인지를 확인하여 문제를 해결했다.

 

코드

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

vector<string> output;
int n;

struct node {

	int finish; //해당 노드에서 끝나는 문자열의 개수
	int alpha_cnt[26]; //해당 노드에서 나아가는 알파벳별 개수
	node* children[26];
};

node* New_node()
{
	node* ret = new node();

	ret->finish = 0;
	for (int i = 0; i < 26; i++)
	{
		ret->children[i] = NULL;
		ret->alpha_cnt[i] = 0;
	}

	return ret;
}

//트라이에 넣기
void Insert(node*& here, string input, int index)
{
	//모든 알파벳을 다 넣었을때
	if (index == input.size())
	{
		here->finish++;

		return;
	}

	if (here->children[input[index] - 'a'] != NULL)
	{
		here->alpha_cnt[input[index] - 'a']++;
		Insert(here->children[input[index] - 'a'], input, index + 1);
	}

	else
	{
		here->children[input[index] - 'a'] = New_node();

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

string Check(node*& here, string input, int index, string ret)
{
	//가능한 별칭이 없는 경우
	if (input.size() == index)
	{
		//같은 닉네임으로 가입한 사람의 수 계산
		int x = here->finish;

		if (x == 1)
			return ret;

		else
			return ret + to_string(x);
	}

	//해당 접두사가 이전에 가입한 닉네임의 접두사와 겹치지 않을때
	if (here->alpha_cnt[input[index] - 'a'] == 1)
	{
		return ret + input[index];
	}

	return Check(here->children[input[index] - 'a'], input, index + 1, ret + input[index]);
}

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

	cin >> n;

	node* root = New_node();

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

		Insert(root, input, 0);

		string result = Check(root, input, 0, "");
		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++)
		cout << output[i] << "\n";

	return 0;
}