[Programmers] 2020 신입 개발자 블라인드 채용 1차 코딩 테스트 - 가사 검색

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

 

문제 풀이:

단순히 trie를 짠 다음에 queries[i]에서 '?'가 나오면 해당 trie 노드에서 갈라지는 모든 곳으로 가도록 구현했더니 효율성 테스트에서 시간 초과가 났다. -> 정적 트라이로 풀어도 ㅠㅠ

해설을 보니 words를 trie에 insert할 때, 원래 문자열들로 만드는 트라이 하나, 뒤집은 문자열로 만드는 트라이 하나, 이렇게 두 개 만들어 각각 넣어주면 된다고 한다. 그리고 문자열 길이마다 트라이를 미리 만들어 놓고, 길이에 맞는 트라이에 삽입함으로써 ?를 만났을 때 바로 가능한 문자들의 개수를 리턴해주고 끝나면 된다.

가능한 문자들의 개수는 처음 words를 입력할 때, (해당 노드의) 자식의 개수를++ 해주면서 forwarding하면 된다.

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>

#include <string.h>
#define MAXLEN 10000
#define NUMMAX 1000001  // 전체 가사 단어 길이의 합
using namespace std;


struct trie {
	trie *next[26];
	int child;

	trie() {
		fill(next, next + 26, nullptr);
		child = 0;
	}
	~trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i]) delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key=='\0') return;

		int num = *key - 'a';
		if (!next[num]) next[num] = new trie();

		child++;
		next[num]->insert(key+ 1); 
	}
	int func(const char *key) {
		if (*key=='\0') return child;

		if (*key == '?') return child;
		
		int num = *key - 'a';
		if (!next[num]) return 0;
		
		return next[num]->func(key+1);
	}
};
trie tr[20002];
vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;
	
	for (int i = 0; i < words.size(); i++) {
		int len = words[i].size();
		const char* tmp = words[i].c_str();
		tr[len].insert(tmp);
		reverse(words[i].begin(), words[i].end());
		tmp = words[i].c_str();
		tr[MAXLEN + len].insert(tmp);
	}
	for (int i = 0; i < queries.size(); i++) {
		int len = queries[i].size();
		const char* tmp = queries[i].c_str();
		if (queries[i][0] == '?') {
			reverse(queries[i].begin(), queries[i].end());
			tmp = queries[i].c_str();
			answer.push_back(tr[MAXLEN + len].func(tmp));
		}
		else answer.push_back(tr[len].func(tmp));
	}
	return answer;
}


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

	vector<string> words, queries;
	vector<int> res;

	for (int i = 0; i < 6; i++) {
		string s;
		cin >> s;
		words.push_back(s);
	}
	for (int i = 0; i < 5; i++) {
		string s;
		cin >> s;
		queries.push_back(s);
	}
	res = solution(words, queries);
	for (int i = 0; i < 5; i++) {
		cout << res[i] << " ";
	}

	//cout << solution(input,3) << '\n';
	return 0;
}

/*
frodo front frost frozen frame kakao
fro?? ????o fr??? fro??? pro?
*/