[백준/BOJ] 백준 19585번 : 전설
2021. 9. 4. 12:38ㆍ알고리즘 문제풀이
https://www.acmicpc.net/problem/19585
색상 트라이와 닉네임 트라이를 만들었다. 닉네임을 닉네임 트라이에 넣을 때는 닉네임을 거꾸로 해서 넣었는데, 이유는 팀명이 주어졌을 때 거꾸로 해서 닉네임이 될 수 있는 것을 빨리 찾기 위해서이다. 그래서 팀명이 주여 졌을 때 앞에서부터 색상을 찾고 뒤에서부터 닉네임을 찾아서 색상과 닉네임의 경계가 잘 맞으면 수상할 수 있는 팀으로 하여 문제를 해결했다.
코드
#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;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 15972번 : 물탱크 (0) | 2021.11.20 |
---|---|
[백준/BOJ] 백준 12784번 : 인하니카 공화국 (0) | 2021.11.20 |
[백준/BOJ] 백준 20188번 : 등산 마니아 (0) | 2021.09.04 |
[백준/BOJ] 백준 2325번 : 개코전쟁 (0) | 2021.09.04 |
[백준/BOJ] 백준 7469번 : K번째 수 (0) | 2021.09.04 |