[Programmers] 가사 검색 - travelbeeee

문제 :  카카오 2020 BLIND RECRUITMENT 가사 검색

---

트라이

 자료구조 트라이를 이용하면 문제에 접근하기는 쉬우나, 그냥 단순하게 트라이를 이용하면 시간초과 때문에 개고생하는 문제입니다. 개고생한 과정을 다뤄보겠습니다...

 

시도 1)

 그냥 트라이를 하나 선언하고 모든 words를 트라이에 insert 한 후 모든 queries를 트라이에서 find 하면서 가능한 모든 경우의 수를 카운트하며 탐색을 진행했다.

int find(const char* key) {
	int cnt = 0;
	if (*key == '\0' && finish == true)
		return 1;
	if (*key == '\0')
		return 0;

	if (*key == '?') {
		for (int i = 0; i < 26; i++)
			if (next[i] != NULL)
				cnt += next[i]->find(key + 1);
	}
	else {
		int curr = *key - 'a';
		if (next[curr] == NULL)
			return 0;
		cnt += next[curr]->find(key + 1);
	}
	return cnt;
}

  들어온 입력을 트라이에서 find 하면서 '?' 를 만나면 지금 노드에서 갈 수 있는 모든 경우를 카운트해줘야하므로 알파벳 소문자의 경우의 수 26가지를 다 탐색하며, 현재 노드에서 갈 수 있는 모든 노드로 다 이동하며 카운트를 해준다. 이러면, 시간 초과를 마주하게 된다. 단순하게 생각해보면 앞 쪽에 물음표들이 연달아 많이 나오는 경우는 처음부터 경우의 수가 굉장히 많아져서 시간 초과에 걸린다는 것을 알 수 있다. 예를 들어, "?????abc" 같은 경우를 find 하려면 최악의 경우 26^5을 다 타고 들어가게 된다.

 

시도 2)

트라이를 하나 더 선언했다. 그냥 트라이와 단어들을 reverse해서 저장하고 있는 트라이를 2개 이용해 queries 중에 앞이 '?' 이면 reverseTrie 에서 find를 하고, 아니라면 그냥 트라이에서 find를 진행했다.

 마찬가지로, 시간 초과를 마주하게 된다... "?????" 과 같이 모두 물음표인 경우 때문에 시간 초과에 걸린다는 것을 알 수 있었다. 

 

시도 3)

 길이가 i 인 단어들이 몇 개인지 애초에 미리 다 카운트해놓고, 시도2) 처럼 트라이 2개를 이용해서 문제를 해결하려했다. queries 중에 앞도 '?', 뒤도 '?' 라면 전체가 다 물음표인 경우이므로 그냥 길이가 같은 단어가 몇 개인지 return 해주고, 아니라면 트라이 2개를 이용해서 진행했다. 당연히 시간 초과에 봉착했다. 당연히, 앞 뒤가 모두 물음표는 아니지만 "a??????" 와 같이 한 글자만 문자가 나오고 뒤가 다 물음표가 나온다면 시도2)에서 개선된 점이 없다는 것을 알 수 있었다.

 

풀이 )

 결국 물음표를 만나면 탐색을 더 진행하는 것이 아니라 답을 바로 출력해줄 수 있어야된다는 것을 깨달았고, 같은 길이를 가진 words 들끼리 Trie를 선언해줬다. 그리고 trie 에 wordsCnt 라는 int형 변수를 추가해주고, insert 함수를 다음과 같이 수정했다.

	void insert(const char* key) {
		if (*key == '\0')
			finish = true;    //문자열이 끝나는 지점일 경우 표시
		else {
			int curr = *key - 'a';
			if (next[curr] == NULL)
				next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
			wordsCnt++;
			next[curr]->insert(key + 1);    //다음 문자 삽입
		}
	}

 즉, 현재 노드까지 겹치는 단어가 몇 개인지 insert 하면서 카운트를 진행했고, find 중 물음표를 만나면 바로 wordsCnt 값을 return 해주면서 끝내도록 개선했다.

#include<string>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;

struct Trie {
	int wordsCnt;
	bool finish;    //끝나는 지점을 표시해줌
	Trie* next[26];    //26가지 알파벳에 대한 트라이
	Trie() {
		finish = false;
		wordsCnt = 0;
		memset(next, 0, sizeof(next));
	}
	~Trie() {
		for (int i = 0; i < 26; i++)
			if (next[i])
				delete next[i];
	}

	void insert(const char* key) {
		if (*key == '\0')
			finish = true;    //문자열이 끝나는 지점일 경우 표시
		else {
			int curr = *key - 'a';
			if (next[curr] == NULL)
				next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
			wordsCnt++;
			next[curr]->insert(key + 1);    //다음 문자 삽입
		}
	}

	int find(const char* key) {
		int cnt = 0;
		//cout << "현재 " << *key << "를 탐색중이고 " << wordsCnt << "는다음과같습니다.\n";
		if (*key == '\0' && finish == true)
			return 1;
		if (*key == '\0')
			return 0;

		if (*key == '?') {
			return wordsCnt;
		}
		else{
			int curr = *key - 'a';
			if (next[curr] == NULL)
				return 0;
			cnt += next[curr]->find(key + 1);
		}
		return cnt;
	}
};

vector<int> solution(vector<string> words, vector<string> queries) {
	Trie* trie[10001];
	Trie* reverseTrie[10001];
	for (int i = 1; i < 10001; i++){
		trie[i] = new Trie();
		reverseTrie[i] = new Trie();
	}

	for (int i = 0; i < words.size(); i++){
		trie[words[i].length()]->insert(words[i].c_str());
		reverse(words[i].begin(), words[i].end());
		reverseTrie[words[i].length()]->insert(words[i].c_str());
	}

	vector<int> answer;
	for (int i = 0; i < queries.size(); i++) {
		int ans;
        if(queries[i][0] == '?'){
			reverse(queries[i].begin(), queries[i].end());
			ans = reverseTrie[queries[i].length()]->find(queries[i].c_str());
		}
		else{
			ans = trie[queries[i].length()]->find(queries[i].c_str());
		}
		answer.push_back(ans);
	}
	return answer;
}

---