C++ / 백준 / 19585 / 전설

문제

 

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

19585번: 전설

문제풀이

 

색상은 트라이, 닉네임은 set을 이용해 풀었다.

처음에는 둘 다 해시로 풀어서 안되길래 라빈카프로 바꿔서 풀어봤는데도 안 됐다.

그래서 트라이 + 해시로 풀어봤는데 15%에서 계속 틀리길래 검색을 해봤는데 반례가 하나도 없길래 직접 생각해 봤다.

 

처음에는 트라이로 검색해 나가면서 isEnd가 true이면 break를 통해 색상은 더 이상 찾지 않고 나머지 문자열이 닉네임에 있는지 판별을 하는 식으로 했다.

하지만 색상이 red, re, r 이렇게 있고 닉네임이 shift일 때

redshift, reshift는 No가 출력되는 반례가 있었다.

그래서 현재 문자가 어떤 색상의 끝일 때 나머지 문자열이 닉네임에 없을 때, 다시 다음 색상을 찾는 과정을 하도록 했다.

 

Color* ptr;

int Color::search(char& c) {
	if (ptr->child.find(c) == ptr->child.end()) return -1;
	else {
		if (ptr->child[c]->isEnd == true) {
			ptr = ptr->child[c];
			return 1;
		}
		else {
			ptr = ptr->child[c];
			return 0;
		}
	}
}

ptr을 전역변수로 두고 문자를 하나하나씩 보면서 색상에 해당 문자가 없으면 -1을,

해당 문자가 색상의 끝이면 1을,

해당 문자가 끝이 아니면 0을 return 하도록 했다.

-1이 return 되면 NO를 출력하면 되고, 1이 return 되면 나머지 문자열에 대해 닉네임이 있는지를 판별하면 된다.

0을 return 하는 경우는 다음 문자를 계속 탐색하라는 의미이다.

 

코드

#include <bits/stdc++.h>
using namespace std;

struct Color {
	map<char, Color*> child;
	bool isEnd;

	Color() : child(), isEnd(false) {}
	~Color() {
		child.clear();
	}

	void insert(string& str) {
		Color* color = this;
		for (int idx = 0; idx < str.size(); ++idx) {
			if (color->child.find(str[idx]) == color->child.end()) {
				color->child[str[idx]] = new Color();
			}
			color = color->child[str[idx]];
			if (idx + 1 == str.size()) color->isEnd = true;
		}
	}
	int search(char& c);
};

Color* ptr;

int Color::search(char& c) {
	if (ptr->child.find(c) == ptr->child.end()) return -1;
	else {
		if (ptr->child[c]->isEnd == true) {
			ptr = ptr->child[c];
			return 1;
		}
		else {
			ptr = ptr->child[c];
			return 0;
		}
	}
}

unordered_set<string>names;

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

	int C(0), N(0);
	cin >> C >> N;

	Color* color = new Color();
	string input("");
	for (int idx = 0; idx < C; ++idx) {
		cin >> input;
		color->insert(input);
	}
	for (int idx = 0; idx < N; ++idx) {
		cin >> input;
		names.insert(input);
	}

	int Q(0), ret(0);
	cin >> Q;

	for (int idx = 0; idx < Q; ++idx) {
		cin >> input;
		ptr = color;
		bool flag(false);
		for (int idx2 = 0; idx2 < input.size(); ++idx2) {
			ret = color->search(input[idx2]);
			if (ret == 1) {
				string name = input.substr(idx2 + 1);
				if (names.find(name) != names.end()) {
					flag = true;
					break;
				}
			}
			else if (ret == -1) {
				break;
			}
		}
		if (flag == true) cout << "Yes\n";
		else cout << "No\n";
	}
}