[BOJ 19585] 전설

 

[문제]

 

www.acmicpc.net/problem/19585

19585번: 전설

 

[난이도]

 

- Platinum 3 (solved.ac 20.12.10 기준)

 

 

[필요 개념]

 

- 트라이 (Trie) / (해싱)

 

 

[풀이] 

 

처음에는 색상과 닉네임을 모두 하나의 트라이에 넣고, 팀명을 탐색하면서 색상과 일치하는 모든 위치를 찾아

해당 위치 이후의 문자열들을 잘라 다시 트라이에 넣어서 닉네임과 일치하는지를 체크하였는데 83%에서 TLE가 발생했다. 

만약 팀명이 2000자이고, 1 ~ 1000번째까지 모두 색상과 일치하고, 1001번째 ~ 2000번째까지 모두 닉네임과 일치한다면 시간이 매우 오래 걸릴 것 같다. 

색상은 한번 탐색으로 일치하는 모든 위치를 다 구할 수 있지만, 닉네임은 각 위치별로 잘린 문자열들을 모두 탐색해야 하기 때문에 시간이 오래 걸린다. 

 

따라서 닉네임과 일치하는지를 확인할 때, 색상과 마찬가지로 한 번에 닉네임과 일치하는 모든 부분을 찾아준다면 결국 O(팀명의 길이)로 수상 여부를 파악할 수 있다. 

 

핵심 아이디어는, 닉네임을 뒤집어서 다른 트라이에 넣어두고, 팀명도 뒤집어서 해당 트라이에서 탐색해주는 것이다. 

그러면 닉네임도 색상과 같은 방식들로 일치하는 각 위치들이 나오게 되고, 최종적으로 색상의 위치와 닉네임의 위치가 이웃하면 해당 팀명은 수상 가능하다. 

 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define ini(x, y) memset(x, y, sizeof(x));
using namespace std;
int chk[2001];
struct Trie {
	map<char, Trie*> ch;
	bool end;
	Trie() {
		end = false;
		ch.clear();
	}
	void insert(const char* s) {
		if (!*s) { 
			end = true;
			return;
		}
		int now = *s - 'a';
		if (ch.find(now) == ch.end()) ch[now] = new Trie;
		ch[now]->insert(s + 1);
	}
	void find(const char* s, int k, bool color) {
		if (end) chk[k]++;
		if (!*s) return;
		int now = *s - 'a';
		if (ch.find(now) == ch.end()) return;
		ch[now]->find(s + 1, color ? k + 1 : k-1 , color);
	}
};
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int C, N; cin >> C >> N;
	Trie* root = new Trie;
	Trie* root2 = new Trie;
	for (int i = 1; i <= C; i++) {
		string s; cin >> s;
		root->insert(s.c_str());
	}
	for (int i = 1; i <= N; i++) {
		string s; cin >> s;
		reverse(all(s));
		root2->insert(s.c_str());
	}
	int Q; cin >> Q;
	while (Q--) {
		string s; cin >> s;
		ini(chk, 0);
		root->find(s.c_str(), 0, true);
		reverse(all(s));
		root2->find(s.c_str(), sz(s), false);
		bool ans = false;
		for (int i = 0; i < sz(s); i++) if (chk[i] == 2) { ans = true; break; }
		if (ans) cout << "Yes\n";
		else cout << "No\n";
	}
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^