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

출처: 2020 KAKAO Blind Recruitment

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

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

문제에 대한 자세한 내용은 링크를 통해 직접 확인하시기 바랍니다.

 

이분 탐색 문제를 풀던 중 나온, 카카오 기출문제들이 으레 그렇듯 꽤 난이도 있는 문제입니다.

정확히는 정석대로 이분 탐색을 구현하는 것이 아닌, lower_bound와 upper_bound 함수를 이용하여 구현하는 방식입니다.

 

문제를 접근한 순서는 다음과 같습니다.

1. 각 단어를 길이에 따라 나눈다.
2. 각 단어 길이 배열을 알파벳 순서로 정렬한다.
3. 이진 탐색을 통해 쿼리의 단어로 시작하는 마지막 단어와 첫 단어의 인덱스를 구하고, 그 차이를 구합니다. (?를 a와 z로 대체한 후, 그 사이 구간의 갯수를 구하면 편합니다.)
4. 접두사가 ?로 시작하는 쿼리의 경우, 계산을 위해 reverse를 이용하여 문자열을 뒤집은 후 2~3의 과정을 수행한다.
5. 각 결과를 정답 배열에 저장한다.

별도로 두 개의 함수를 작성하였습니다.

countByRange 함수는 주어진 정렬된 문자열 배열 내에서, 시작점과 끝점 사이의 갯수를 구하는 함수입니다.

lower_bound와 upper_bound 함수를 사용했고, 예를 들어 찾고자 하는 단어가 'fro??' 라면, froaa ~ frozz 사이의 단어의 수를 구합니다.

replaceAll 함수는 문자열 내의 특정 문자를 다른 문자로 바꿔주는 함수입니다. ?를 a 또는 z로 바꾸는 역할을 합니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	#define MAX_N 10001
	int countByRange(vector<string> &v, string leftValue, string rightValue) {
	vector<string>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightValue);
	vector<string>::iterator leftIndex = lower_bound(v.begin(), v.end(), leftValue);
	return rightIndex - leftIndex;
	}
	string replaceAll(string str, string from, string to) {
	string result = str;
	int pos = 0;
	while ((pos = result.find(from, pos)) != string::npos) {
	result.replace(pos, from.size(), to);
	pos += to.size();
	}
	return result;
	}
	vector<string> arr[MAX_N];
	vector<string> reversed_arr[MAX_N];
	vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;
	for (int i = 0; i < words.size(); i++) {
	string word = words[i];
	arr[word.size()].push_back(word);
	reverse(word.begin(), word.end());
	reversed_arr[word.size()].push_back(word);
	}
	for (int i = 0; i < MAX_N; i++) {
	sort(arr[i].begin(), arr[i].end());
	sort(reversed_arr[i].begin(), reversed_arr[i].end());
	}
	for (int i = 0; i < queries.size(); i++) {
	string q = queries[i];
	int result = 0;
	if (q[0] != '?')
	result = countByRange(arr[q.size()], replaceAll(q, "?", "a"), replaceAll(q, "?", "z"));
	else {
	reverse(q.begin(), q.end());
	result = countByRange(reversed_arr[q.size()], replaceAll(q, "?", "a"), replaceAll(q, "?", "z"));
	}
	answer.push_back(result);
	}
	return answer;
	}

view raw 가사 검색.cpp hosted with ❤ by GitHub