[프로그래머스] 가사 검색

링크

https://programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

풀이

 

각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하는 문제이다.

 

쿼리에서 주어지는 단어와 가사를 비교해야 되는데 일일이 모두 탐색하게 되면 시간 초과가 나는 문제이다.

 

그래서 이 문제를 풀기 위해서는 트라이를 이용해야 되는데.

 

트라이를 만들기 전에 생각을 해봐야 하는 것이 가사와 단어의 길이에 대한 생각이다.

문제에서는 단어와 가사의 길이가 일치해야 하는 조건이 있는데

모든 가사를 하나의 트라이를 만들어 각각 단어에 있는 알파벳의 위치마다 남은 자식의 개수를 카운트해주면 될 수도 있겠지만

 

저는 트라이를 가사 사이즈 별로 구분하여 만들도록 했습니다.

같은 사이즈끼리 트라이를 만들게 되면 남은 자식의 개수를 신경 쓰지 않아도 되기 때문입니다.

 

그래서 가사를 이용하여 트라이를 만들때 같은 알파벳이 나오면 자식의 개수를 하나씩 증가시켜 주며 만들었습니다.

 

이렇게 가사의 사이즈로 구분하여 트라이를 만든 후

 

단어를 입력받으려 보니 '?'가 앞 뒤로 나오는 것을 알 수 있습니다

단어를 검색할 때? 가 없는 부분부터 시작을 해야 되는데 그래서

 

가사를 이용하여 Trie를 가사의 앞에서 시작하는 것과 가사의 뒤에서부터 시작하는 2개의 트라이를 만들었다.

 

이후 '?'의 위치를 찾은 후 어느 위치에서 시작하는 트라이를 탐색할 것인지 확인하고

트라이에서 탐색을 돌려 검색할 수 있는 단어의 개수를 찾았다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 33
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

struct Trie {
	Trie *node[SIZE];
	bool finish, child;
	int child_cnt = 0;
	Trie() {
		fill(node, node + SIZE, nullptr);
		finish = child = child_cnt = false;
	}

	~Trie() {
		for (int i = 0; i < SIZE; i++) {
			if (node[i])
				delete node[i];
		}
	}

	void insert(const string &word, int index,int toggle) {
		child_cnt++;
		if (toggle == 1) {//왼쪽에서 오른쪽으로
			if (index >= word.size()) {
				finish = true;
				return;
			}
		}		
		else if(toggle == -1) {//오른쪽에서 왼쪽으로
			if (index < 0) {
				finish = true;
				return;
			}
		}

		int alpa_index = word[index] - 'a';
		if (node[alpa_index] == NULL) {
			node[alpa_index] = new Trie();
			child = true;
		}

		node[alpa_index]->insert(word, index + toggle, toggle);
	}

	int find(const string &word, int index,int toggle) {
		int res = 0;
		int word_index = word[index] - 'a';

		//현재 단어가 '?' 이면 밑에 있는 자식들의 개수를 리턴
		if (word[index] == '?')
			return child_cnt;

		//단어의 끝날 때 0 리턴
		if (node[word_index] == NULL) {
			return 0;
		}
		
		if (toggle == 1) { //오른쪽에서 왼쪽으로
			res = node[word_index]->find(word, index + toggle, toggle);
		}
		else if (toggle == -1) {//왼쪽에서 오른쪽으로
			res = node[word_index]->find(word, index + toggle, toggle);
		}

		return res;
	}
};
Trie left_right[10010];
Trie right_left[10010];

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

	for (auto word : words) {
		//가사의 길이를 분류하여 트라이를 만듬
		int w_size = word.size();
		left_right[w_size].insert(word, 0, 1);
		right_left[w_size].insert(word, word.size() - 1, -1);
	}
	vector<int> answer;

	int res = 0;
	for (auto querie : queries) {
		int q_size = querie.size();
		
		//?의 위치 파악
		int toggle = (querie[0] == '?' ? -1 : 1);

		if (toggle == 1) {
			answer.push_back(left_right[q_size].find(querie, 0, toggle));
		}
		else if (toggle == -1) {
			answer.push_back(right_left[q_size].find(querie, querie.size() - 1, toggle));
		}
	}
	return answer;
}


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

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

}