[프로그래머스] [2020카카오공채] 가사 검색

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

코딩테스트 연습 - 가사 검색 | 프로그래머스

 

며칠전 trie 탐색을 공부하고 문제를 풀었던 적이 있었는데, 이 문제를 보고 딱 생각이 나서 적용시켜보았다.

 

정확성은 다 Pass를 했으나, 효율성에서 0이였다.

 

효율성 0 코드

#include <string>
#include <vector>
#include <string.h>
#define ALPHABET 26
using namespace std;
struct trie {
	trie *next[ALPHABET];
	int count[ALPHABET];
	int finish;
	int total;
	trie() : finish(0), total(0){
		memset(next, NULL, sizeof(next));
		memset(count, 0, sizeof(count));
	}
	
	~trie() {
		for (int i = 0; i < ALPHABET; i++) {
			if (next[i] != NULL) {
				delete next[i];
			}
		}
	}

	void insert(const char *str) {
		total++;
		if (*str == '\0') {
			finish = 1;
			return;
		}
		int cur = *str - 'a';
		if (next[cur] == 0) {
			next[cur] = new trie();
		}
		count[cur]++;
		next[cur]->insert(str + 1);
	}

	trie* find(const char *str) {
		if (*str == '\0') {
			return this;
		}
		int cur = *str - 'a';
		if (next[cur] == NULL) {
			return 0;
		}
		return next[cur]->find(str + 1);
	}

	int findPatternKey(const char* str) {
		if (*str == '\0') {
			return finish;
		}
		if (*str == '?') {
			int sum = 0;
			for (int i = 0; i < ALPHABET; i++) {
				if (next[i] == NULL) continue;
				sum += next[i]->findPatternKey(str + 1);
			}
			return sum;
		}
		else {
			int cur = *str - 'a';
			if (next[cur] == NULL) {
				return 0;
			}
			return next[cur]->findPatternKey(str + 1);
		}
	}
};

vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;
	trie *root = new trie();
	for (int i = 0; i < words.size(); i++) {
		root->insert(words[i].c_str());
	}
	for (int i = 0; i < queries.size(); i++) {
		answer.push_back(root->findPatternKey(queries[i].c_str()));
	}
	return answer;
}

 

 

효율성 통과한 소스

 

기존에는 한 트리에 모든 문자열이 담겨있었다면, 이번에는 문자열 길이로 루트배열을 만들어 해당 크기에서만 찾는다.

 

'?' 키워드가 앞에 앞에 있는지 뒤에 있는지를 체크해서 더 효율을 높이려 reverseRoot를 만들었다.

 

?가 앞에 있으면 reverseRoot를, 뒤에 있으면 기존 root를 찾도록 하였다.

 

소스보기

#include <string>
#include <vector>
#include <string.h>
#include <algorithm>
#define ALPHABET 26
using namespace std;
struct trie {
	trie *next[ALPHABET];
	int finish;
	int total;
	trie() : finish(0), total(0){
		memset(next, NULL, sizeof(next));
	}
	
	~trie() {
		for (int i = 0; i < ALPHABET; i++) {
			if (next[i] != NULL) {
				delete next[i];
			}
		}
	}

	void insert(const char *str) {
		if (*str == '\0') {
			finish = 1;
			return;
		}
		int cur = *str - 'a';
		if (next[cur] == 0) {
			next[cur] = new trie();
		}
		
		next[cur]->total++;
		next[cur]->insert(str + 1);
	}

	trie* find(const char *str) {
		if (*str == '\0') {
			return this;
		}
		int cur = *str - 'a';
		if (next[cur] == NULL) {
			return 0;
		}
		return next[cur]->find(str + 1);
	}

	int findPatternKey(const char* str) {
		if (*str == '?') {
			int sum = 0;
			for (int i = 0; i < ALPHABET; i++) {
				if (next[i] == NULL) continue;
				sum += next[i]->total;
			}
			return sum;
		}
		else {
			int cur = *str - 'a';
			if (next[cur] == NULL) {
				return 0;
			}
			if (*(str + 1) == '?') {
				return next[cur]->total;
			}
			return next[cur]->findPatternKey(str + 1);
		}
	}
};

trie* root[10001];
trie* reroot[10001];
vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;
	memset(root, NULL, sizeof(root));
	memset(reroot, NULL, sizeof(reroot));
	for (int i = 0; i < words.size(); i++) {
		int wordsize = words[i].size();
		if (root[wordsize] == NULL) {
			root[wordsize] = new trie();
			reroot[wordsize] = new trie();

			root[wordsize]->insert(words[i].c_str());
			
			reverse(words[i].begin(), words[i].end());
			reroot[wordsize]->insert(words[i].c_str());
		}
		else {
			root[wordsize]->insert(words[i].c_str());
			
			reverse(words[i].begin(), words[i].end());
			reroot[wordsize]->insert(words[i].c_str());
		}
	}
	for (int i = 0; i < queries.size(); i++) {
		if (root[queries[i].size()] == NULL) {
			answer.push_back(0);
		}
		else {
			int front = queries[i][0] == '?' ? 1 : 0;
			if (front) {
				reverse(queries[i].begin(), queries[i].end());
				answer.push_back(reroot[queries[i].size()]->findPatternKey(queries[i].c_str()));
			}
			else {
				answer.push_back(root[queries[i].size()]->findPatternKey(queries[i].c_str()));
			}
		}
	}
	return answer;
}