[2020 KAKAO BLIND RECRUITMENT][C++] 가사 검색

문제 풀어보기

코딩테스트 연습 - 가사 검색

 

TRIE 자료구조를 이용하여 해결하는 문제

일반적인 선형 자료구조로는 절 대 해결 불가 ~ 무조건 시간 초과다

 

<문제 해결 Logic>

1. 와일드카드('?')가 키워드의 접두사 혹은 접미사에 나타나므로, 순방향 트라이/ 역방향 트라이(단어 순서의 방향을 의미함) 두 개를 만들어 주어야 한다.

2. words 벡터의 각 string을 순방향 트라이에 insert 해준다. 또한, 각 string을 reverse 하여 역방향 트라이에 insert 해준다.

3. queries 벡터의 각 키워드의 와일드카드가 접두사/ 접미사에 나타나는 지 확인하고 그에 맞는 트라이에서 키워드 별로 매치된 단어의 수를 구한다.

3-1. Find 함수에서 '?'가 나오기 전까지 Node를 이동시킨다. 현재 글자 다음이 '?' 라면 getCnt()함수를 호출.

3-2. getCnt()에서 현재 Node의 자식 Node가 NULL이 아니면 자식 Node를 현재 Node로. 이를 재귀적으로 수행하다가 현재 글자 다음이 NULL이라면 키워드가 끝난 것이니 이때의 Node의 Finish가 true라면 키워드에 매치가 된 것이다. 따라서 cnt를 1 더해준다. 

 

TRIE 문제 처음 풀어봐서 자료구조 이해하고 구현방법도 찾아보았다.

struct TRIE {
	bool Finish;
	TRIE* Node[26];
	TRIE()
	{
		Finish = false;
		for (int i = 0; i < 26; i++)
			Node[i] = NULL;
	}
}

 

TRIE 구조체를 간단히 살펴보자면, 

Finish 변수와 Node 변수가 있다. Finish는 문자열이 끝났는 지를 알 수 있는 변수이다. Node는 트라이의 노드인데, 이 문제에서 트라이에 들어가는 것은 알파벳이므로 크기를 26칸으로 설정했다.

 

void Insert(char* Str)
	{
		if (*Str == NULL)
		{
			Finish = true;
			return;
		}

		int Cur = *Str - 'a';
		if (Node[Cur] == NULL) Node[Cur] = new TRIE();
		Node[Cur]->Insert(Str + 1);

	}

	void Find(char* Str)
	{
		int Cur = *Str - 'a';
		
		if (Node[Cur] == NULL)
			return;

		if (*(Str+1) == '?')
		{
			Node[Cur]->getCnt(Str);
			return;
		}

		
		return Node[Cur]->Find(Str + 1);
	}

	void getCnt(char* Str)
	{
		if (*(Str + 1) == NULL)
		{
			if (Finish == true)
				cnt++;
			return;
		}
		
		if (Node == NULL)
			return;

		for (int i = 0; i < 26; i++)
		{
			if (Node[i] != NULL)
			{
				Node[i]->getCnt(Str + 1);
			}
		}
	}

 

으악 !!!

정확성 테스트는 통과하는데 효율성 테스트에서 시간초과가 난다,,

 

내일 다시 풀어보쟈.. ㅠ

 

-전체 코드-

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <string.h>
#include <string>

using namespace std;

int cnt = 0;

struct TRIE {
	bool Finish;
	TRIE* Node[26];
	TRIE()
	{
		Finish = false;
		for (int i = 0; i < 26; i++)
			Node[i] = NULL;
	}

	void Insert(char* Str)
	{
		if (*Str == NULL)
		{
			Finish = true;
			return;
		}

		int Cur = *Str - 'a';
		if (Node[Cur] == NULL) Node[Cur] = new TRIE();
		Node[Cur]->Insert(Str + 1);

	}

	void Find(char* Str)
	{
		int Cur = *Str - 'a';
		
		if (Node[Cur] == NULL)
			return;

		if (*(Str+1) == '?')
		{
			Node[Cur]->getCnt(Str);
			return;
		}

		
		return Node[Cur]->Find(Str + 1);
	}

	void getCnt(char* Str)
	{
		if (*(Str + 1) == NULL)
		{
			if (Finish == true)
				cnt++;
			return;
		}
		
		if (Node == NULL)
			return;

		for (int i = 0; i < 26; i++)
		{
			if (Node[i] != NULL)
			{
				Node[i]->getCnt(Str + 1);
			}
		}
	}
};


vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;

	TRIE* Root1 = new TRIE();
	TRIE* Root2 = new TRIE();

	for (int i = 0; i < words.size(); i++)
	{
		char* tmp1 = new char[words[i].length() + 1];
		char* tmp2 = new char[words[i].length() + 1];
		strcpy(tmp1, words[i].c_str());
	
		reverse(words[i].begin(), words[i].end());

		strcpy(tmp2, words[i].c_str());
	
		Root1->Insert(tmp1);
		Root2->Insert(tmp2);
	}
	
	for (int i = 0; i < queries.size(); i++)
	{
		cnt = 0;
		string tmp(queries[i].length(), '?');

		if (strcmp(queries[i].c_str(), tmp.c_str()) == 0)
		{
			int len = queries[i].length();
			for (int j = 0; j < words.size(); j++)
			{
				if (words[j].length() == len)
					cnt++;
			}
		}
		else
		{
			if (queries[i][0] != '?')
			{
				char* tmp = new char[queries[i].length() + 1];
				strcpy(tmp, queries[i].c_str());

				Root1->Find(tmp);

			}
			else
			{
				char* tmp = new char[queries[i].length() + 1];
				reverse(queries[i].begin(), queries[i].end());
				strcpy(tmp, queries[i].c_str());

				Root2->Find(tmp);
			}

		}
		
		cout << cnt << endl;
		answer.push_back(cnt);
	}
	return answer;
}

int main()
{
	vector<string> words = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
	vector<string> queries = { "fro??", "????o", "fr???", "fro???", "pro?", "?????", "??????", "kako?" };

	solution(words, queries);

	return 0;
}