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

프로그래머스 가사 검색 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60060

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

문제 풀이

• 이 문제는 이분 탐색으로 해결했습니다.
• 만약 fro?? 라는 쿼리가 있다면 문자열을 비교하여 froaa - frozz 사이에 포함된 문자열의 개수를 세는 방식입니다. 이를 위해 upper_bound와 lower_bound를 사용했습니다. 
• 물음표가 앞에 있는 ??odo 같은 쿼리의 경우, aaodo - zzodo의 사이가 되기 때문에 위의 논리를 그대로 적용하면 길이가 5인 거의 모든 문자열이 포함되게 됩니다. bakxj 와 같은 문자열도 사전 순으로는 위의 범위에 포함되기 때문입니다. 
• 위의 경우를 방지하기 위해 문자열들을 뒤집어 놓은 vector를 하나 선언하고 쿼리의 물음표가 뒤로 가도록 쿼리를 뒤집어 사용합니다. (??odo -> odo??)  
• 이분 탐색을 위해 string vector를 정렬해야 하는데, query와 같은 길이의 문자만 탐색해야 하기 때문에 먼저 문자열의 길이에 따라 정렬 후 사전 순으로 정렬합니다.

// string vector 정렬 조건
bool cmp(string a, string b) {
    if(a.length() < b.length()) return true; // 길이가 짧은 것이 우선
    else if(a.length() == b.length()) return a < b; // 길이 같다면 사전순
    return false;
}

• 다르게는 문자열의 길이별로 vector를 선언하여 같은 길이의 문자열끼리 모은 후 이분 탐색을 하셔도 됩니다. (효율성 테스트에서는 이 풀이가 더 빠르네요,, ㅎㅎ)

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(string a, string b) {
    if(a.length() < b.length()) return true;
    else if(a.length() == b.length()) return a < b;
    return false;
}

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    vector<string> r_words; // 문자열들 뒤집은 vector
    for(auto word: words) {
        r_words.push_back(string(word.rbegin(), word.rend()));
    }
    
    // 이분탐색 위해 정렬
    sort(words.begin(), words.end(), cmp);
    sort(r_words.begin(), r_words.end(), cmp);
    
    for(auto query: queries) {
        bool flag = query[0] == '?';
        
        // 물음표가 앞에 있을 경우 뒤집기
        if(flag) reverse(query.begin(), query.end());
        
        string start = "", end = "";
        for(auto q: query) {
            if(q == '?') {
                start += 'a';
                end += 'z';
            }
            else {
                start += q;
                end += q;
            }
        }
        
        int count = 0;
        // 물음표가 앞에 있을 경우 문자열들 뒤집은 vector로 계산
        if(flag) count = upper_bound(r_words.begin(), r_words.end(), end, cmp)
                            - lower_bound(r_words.begin(), r_words.end(), start, cmp);
        else count = upper_bound(words.begin(), words.end(), end, cmp) 
                            - lower_bound(words.begin(), words.end(), start, cmp);
        
        answer.push_back(count);
    }
    
    return answer;
}

실행 결과