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

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

프로그래머스

 

아래 카카오 테크 블로그에서도 해설을 볼 수 있다. 

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

이 문제는 효율성 테스트 점수가 있는 문제로 문자열을 하나하나 다 검사하면 효율성 테스트를 통과할 수 없다.

트라이 자료구조나 이분 탐색으로 효율성 테스트를 통과할 수 있는데 나는 이분 탐색으로 풀었다.

 

먼저 이분 탐색을 하기 위해서는 가사에 사용된 모든 단어들이 담긴 words를 정렬해줘야 하는데 정렬 기준이 되는 비교 함수를 만들어줘야 한다. 비교 함수는 단어의 길이로 먼저 오름차순 정렬하고 길이가 같다면 사전 순으로 정렬해준다.

 

["frodo", "front", "frost", "frozen", "frame", "kakao"]

문제의 예제로 예를 들면 위의 words 배열은 아래와 같이 될 것이다.

["frame", "frodo", "front", "frost", "kakao", "frozen"]

 

그리고 "????o"와 같이 ?가 접두사로 주어지는 경우에는 문자열의 뒤쪽부터 검사를 해줘야 하므로 words의 각 문자열을 뒤집은 배열 rwords를 만들어서 위와 마찬가지로 단어 길이, 사전 순 순서로 정렬해준다. 그러면 rwords는 아래와 같이 될 것이다.

["emarf", "oakak", "odorf", "tnorf", "tsorf", "nezorf"]

 

 

 

 

words와 rwords 모두 정렬을 해줬다면 이제 각 쿼리에 대해서 쿼리의 0번째 문자가 '?'인지 아닌지에 따라 나눠서 구현한다.

 

쿼리의 0번째 문자가 '?'라면

'?'가 접두사에 있는 경우이므로 문자열을 뒤집어준 배열인 rwords에서 탐색해야 한다. 쿼리 역시 마찬가지로 뒤집어준다. 문제 예제의 "????o" 같은 경우에는 "o????"이 될 것이다.

그러면 이제 "????"의 위치에 각각 "aaaa"와 "zzzz"를 넣고 lower_boud와 upper_bound를 사용해서 이분 탐색을 해준다. 이때도 비교 함수를 기준으로 탐색하도록 정렬할 때 사용한 비교 함수를 함께 넣어줘야 한다.

 

(참고로 lower_bound는 찾으려는 key값 이상의 값이 처음 나타나는 위치를 반환하고 upper_bound는 찾으려는 key값을 초과하는 값이 처음 나타나는 위치를 이분 탐색으로 반환한다.)

 

각 가사 단어는 오직 알파벳 소문자로만 구성되어 있다고 문제 조건에 나와있기 때문에 사전 순으로 가장 작은 값인 a와

가장 큰 값인 z로 채워 해당 범위의 최솟값과 최댓값을 만들어주는 것이다. ozzzz보다 큰 값이 처음 나타나는 위치에서 oaaaa 이상의 값이 처음 나타나는 곳의 위치를 빼주면 "o????"에 해당하는 문자열들의 개수를 구할 수 있다.

 

upperbound는 3번 위치인 tnorf가 되고 lowerbound값은 1번 위치인 oakak가 되므로 3-1을 해주면 2개인 것을 구할 수 있다.

["emarf", "oakak", "odorf", "tnorf", "tsorf", "nezorf"]

 

 

쿼리의 0번째 문자가 '?'가 아니라면

'?'가 접미사에 있는 경우이므로 가사의 앞부분을 검사하면 되므로 words배열에서 탐색한다.

탐색하는 방법은 위와 마찬가지로 "??"부분에 "aa"와 "zz"를 넣은 경우에 대해 각각 lower_bound와 upper_bound를 구해서 빼주면 된다.

예를 들어, 쿼리가 "fro??"라고 했을 때 "froaa"의 lower_bound값을 구하면 1번째 위치가 나오고 "frozz"의 upper_bound값을 구하면 4번째 위치가 나온다. 그러면 4 - 1을 해면 3이 나와서 아래 표시된 3가지 문자열이 "fro??"에 해당하는 문자열들이다.

["frame", "frodo", "front", "frost", "kakao", "frozen"]

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
 
//길이로 먼저 정렬하고 길이가 같다면 사전순으로 정렬
bool comp(string a, string b) {
    if (a.length() < b.length())
        return true;
    else if (a.length() == b.length())
        if (a < b) return true;
    return false;
}
 
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
 
    //rwords 벡터에 단어를 뒤집어서 저장
    vector<string> rwords = words;
    int size = rwords.size();
    for (int i = 0; i < size; i++) reverse(rwords[i].begin(), rwords[i].end());
 
 
    //comp 기준 정렬
    sort(words.begin(), words.end(), comp);
    sort(rwords.begin(), rwords.end(), comp);
 
 
    int len, lo, hi;
    int idx;
    for (string query : queries) {
        len = query.length();
        
        if (query[0] == '?') {
            //?가 접두사에 있는 경우
            reverse(query.begin(), query.end()); //키워드도 뒤집어준다.
            idx = query.find_first_of('?');
 
            for (int i = idx; i < len; i++) query[i] = 'a';
            lo = lower_bound(rwords.begin(), rwords.end(), query, comp) - rwords.begin();
 
            for (int i = idx; i < len; i++) query[i] = 'z';
            hi = upper_bound(rwords.begin(), rwords.end(), query, comp) - rwords.begin();
        }
        else {
            //?가 접미사에 있는 경우
            idx = query.find_first_of('?');
 
            for (int i = idx; i < len; i++) query[i] = 'a';
            lo = lower_bound(words.begin(), words.end(), query, comp) - words.begin();
 
            for (int i = idx; i < len; i++) query[i] = 'z';
            hi = upper_bound(words.begin(), words.end(), query, comp) - words.begin();            
        }
 
        answer.push_back(hi - lo);
    }
 
    return answer;
}