[백준/BOJ] 백준 19585번 : 전설

2021. 9. 4. 12:38알고리즘 문제풀이

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

 

19585번: 전설

Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수

www.acmicpc.net

색상 트라이와 닉네임 트라이를 만들었다. 닉네임을 닉네임 트라이에 넣을 때는 닉네임을 거꾸로 해서 넣었는데, 이유는 팀명이 주어졌을 때 거꾸로 해서 닉네임이 될 수 있는 것을 빨리 찾기 위해서이다. 그래서 팀명이 주여 졌을 때 앞에서부터 색상을 찾고 뒤에서부터 닉네임을 찾아서 색상과 닉네임의 경계가 잘 맞으면 수상할 수 있는 팀으로 하여 문제를 해결했다.

 

코드

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

int c, n;
int q;
vector<string> output;

struct node {
	bool finished;
	//node* children[26];
	//메모리 초과 나와서 map
	map<char, node*> children;
};

node* color;
node* name;

vector<int> check_color(1001);
vector<int> check_name(1001);

node* MakeNode()
{
	node* ret = new node();
	ret->finished = false;

	return ret;
}

void Insert(node*& here, string& input, int index)
{
	if (input.size() == index)
	{
		here->finished = true;
		return;
	}

	if (here->children.count(input[index]) == 0)
	{
		here->children.insert(make_pair(input[index], MakeNode()));
		Insert(here->children[input[index]], input, index + 1);
	}

	else
	{
		Insert(here->children[input[index]], input, index + 1);
	}

}

void FindColor(node*& here, string& input, int index)
{
	if (here->finished == true)
	{
		check_color[index] = 1; //index 길이의 색깔이 있다고 체크
	}

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

	if (here->children.count(input[index]) == 0)
		return;

	FindColor(here->children[input[index]], input, index + 1);
}

void FindName(node*& here, string& input, int index)
{
	if (here->finished == true)
	{
		check_name[(input.size() - 1) - index] = 1; //(input.size() - 1) - index 길이의 닉네임이 있다고 체크
	}

	if (index == -1)
		return;

	if (here->children.count(input[index]) == 0)
		return;

	FindName(here->children[input[index]], input, index - 1);
}
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	color = MakeNode();
	name = MakeNode();

	cin >> c >> n;

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

		Insert(color, input, 0);
	}

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

		//닉네임을 거꾸로해서 트라이에 넣는다 (팀명이 주어졌을때 거꾸로 해서 닉네임이 될수 있는것을 빨리 찾기 위해)
		reverse(input.begin(), input.end());
		Insert(name, input, 0);
	}

	cin >> q;

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

		//check초기화
		for (int i = 0; i < 1001; i++)
		{
			check_color[i] = 0;
			check_name[i] = 0;
		}

		FindColor(color, input, 0);
		FindName(name, input, input.size() - 1); //닉네임은 트라이에 거꾸로 들어 있으므로 input.size() - 1 번째 부터 확인한다

		bool yes_check = false;
		for (int i = 1; i <= 1000; i++)
		{
			if (check_color[i] == 1 && check_name[input.size() - i] == 1)
			{
				yes_check = true;
				break;
			}
		}

		if (yes_check == true)
			output.push_back("Yes");
		else
			output.push_back("No");
	}

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

	return 0;
}