[PS] 전설 / C++ (백준 19585번)

전설 (백준 19585번)

 

총 13번의 오답을 받으며 오랜만에 머리 터질 정도로 시간 복잡도, 공간 복잡도 둘 다 생각하게 하는 문제였다.

 

풀이 과정

Trie 자체를 최적화(재귀 >> 동적으로)하여 시간을 줄이면서, 동시에 Trie와 unordered_set을 함께 사용해서 시간, 메모리 둘 다 잡아 AC를 받을 수 있다. Trie를 잘 구현하여 최적화하고 set만 적절하게 사용하면 쉽게 풀리는 문제인데, 그 과정까지 시행 착오가 필요하다.

 

메모리 초과 코드 (Double Trie)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<map>
using namespace std;

stack<char *> st;

struct Trie {
	bool finish;
	Trie* next[26];

	Trie() :finish(0) {
		for (int i = 0; i < 26; i++)
			next[i] = NULL;
	}

	void insert(char* key) {
		Trie* cur = this;
		for (int i = 0; *(key + i); i++) {
			int curA = *(key + i) - 'a';
			if(cur->next[curA]==NULL)cur->next[curA] = new Trie();
			cur = cur->next[curA];
		}
		cur->finish = true;
		return;
	}

	bool find_name(char* key) {
		Trie* cur = this;
		for (int i = 0; ; i++) {
			if (*(key + i) == '\0') {
				if (cur->finish)return true;
				else return false;
			}
			int curA = *(key + i) - 'a';
			if (cur->next[curA] == NULL)return false;
			cur = cur->next[curA];
		}
	}

	void find_col(char* key) {
		Trie* cur = this;
		for (int i = 0; *(key + i); i++) {
			if (cur->finish)st.push(key + i);
			int curA = *(key + i) - 'a';
			if (cur->next[curA] == NULL)return;
			cur = cur->next[curA];
		}
	}
};

char a[1001], team[2001];

int main()
{
	Trie* col = new Trie();
	Trie* nickN = new Trie();
	int n, c;
	scanf("%d %d", &n, &c);
	for (int i = 0; i < n; i++) {
		scanf("%s", a);
		col->insert(a);
	}
	for (int i = 0; i < c; i++) {
		scanf("%s", a);
		nickN->insert(a);
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", team);
		col->find_col(team);
		int TF = 0;
		while (!st.empty()) {
			char* mid = st.top();
			st.pop();
			if (nickN->find_name(mid)) {
				TF = 1;
				break;
			}
		}
		if (TF)printf("Yes\n");
		else printf("No\n");
		while (!st.empty())st.pop();
	}
	return 0;
}

 

시간 초과 코드 (Map 사용)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<map>
using namespace std;

stack<char *> st;

struct Trie {
	bool finish = 0;
	map<char, Trie*> next;

	void insert(char* key) {
		Trie* cur = this;
		for (int i = 0; *(key + i); i++) {
			if (cur->next.find(*(key + i)) == cur->next.end())cur->next[*(key + i)] = new Trie();
			cur = cur->next[*(key + i)];
		}
		cur->finish = true;
		return;
	}

	bool find_name(char* key) {
		Trie* cur = this;
		for (int i = 0; ; i++) {
			if (*(key + i) == '\0') {
				if (cur->finish)return true;
				else return false;
			}
			if (cur->next.find(*(key + i)) == cur->next.end())return false;
			cur = cur->next[*(key + i)];
		}
	}

	void find_col(char* key) {
		Trie* cur = this;
		for (int i = 0; *(key + i); i++) {
			if (cur->finish)st.push(key + i);
			if (cur->next.find(*(key + i)) == cur->next.end())return;
			cur = cur->next[*(key+i)];
		}
	}
};

char a[1001], team[2001];

int main()
{
	Trie* col = new Trie();
	Trie* nickN = new Trie();
	int n, c;
	scanf("%d %d", &n, &c);
	for (int i = 0; i < n; i++) {
		scanf("%s", a);
		col->insert(a);
	}
	for (int i = 0; i < c; i++) {
		scanf("%s", a);
		nickN->insert(a);
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", team);
		col->find_col(team);
		int TF = 0;
		while (!st.empty()) {
			char* mid = st.top();
			st.pop();
			if (nickN->find_name(mid)) {
				TF = 1;
				break;
			}
		}
		if (TF)printf("Yes\n");
		else printf("No\n");
		while (!st.empty())st.pop();
	}
	return 0;
}

 

정답 코드 (Trie + unordered_set)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>
using namespace std;

unordered_set<string> nickname;

struct Trie {
	bool finish;
	Trie* next[26];

	Trie() :finish(0) {
		memset(next, 0, sizeof(next));
	}

	void insert(char* key) {
		Trie* cur = this;
		for (int i = 0; *(key + i); i++) {
			int curA = *(key + i) - 'a';
			if(cur->next[curA]==NULL)cur->next[curA] = new Trie();
			cur = cur->next[curA];
		}
		cur->finish = true;
		return;
	}

	bool find_col(char* key) {
		Trie* cur = this;
		for (int i = 0; *(key + i); i++) {
			if (cur->finish) {
				if (nickname.count(key + i))return true;
			}
			int curA = *(key + i) - 'a';
			if (cur->next[curA] == NULL)return false;
			cur = cur->next[curA];
		}
		return false;
	}
};

char a[1001], team[2001];

int main()
{
	Trie* col = new Trie();
	Trie* nickN = new Trie();
	int n, c;
	scanf("%d %d", &n, &c);
	for (int i = 0; i < n; i++) {
		scanf("%s", a);
		col->insert(a);
	}
	for (int i = 0; i < c; i++) {
		scanf("%s", a);
		nickname.insert(a);
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", team);
		int TF = col->find_col(team);
		if (TF)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}