[c++][프로그래머스] 순위 검색

프로그래머스 순위 검색 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

문제 풀이

• 이 문제는 비트마스킹을 사용해 가능한 모든 경우의 수를 만들어 map에 저장하고, query에 따라 해당 점수 이상이 몇 명인지 lower_bound를 사용해 구하여 해결했습니다. 
• 비트마스킹 사용시에 for문을 16번 반복하는데 이것은 각 항목별로 자신의 항목 or "-"에 포함될 수 있기때문에 16번(2^4) 반복합니다. 
  • 예를 들어 입력이 "java backend junior pizza 150"일 경우 다음과 같습니다. 
    • 0 (0000) -> key = "----"
    • 1 (0001) -> key = "java---"
    • 5 (0101) -> key = "java-junior-"
    • 15 (1111) -> key = "javabackendjuniorpizza"

코드

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

using namespace std;

vector<string> data_parse(string data) {
    vector<string> ret;
    string tmp = "";
    
    for(auto c: data) {
        if(c == ' ') {
            if(tmp != "and") ret.push_back(tmp);
            tmp = "";
        }
        else tmp += c;
    }        
    
    ret.push_back(tmp);
    return ret;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    unordered_map<string, vector<int>> db;
    for(auto inf: info) {
        vector<string> key = data_parse(inf);
        
        for(int i=0; i<16; ++i) {
            string tmp = "";            
            for(int j=0; j<4; ++j) {
                tmp += (i & (1 << j)) ? key[j] : "-";
            }
            db[tmp].push_back(stoi(key[4]));
        }
    }
    
    // lower_bound 사용 위해 sort
    for(auto &iter: db) sort(iter.second.begin(), iter.second.end());    
    
    for(auto q: query) {
        vector<string> key = data_parse(q);
        
        string k = key[0] + key[1] + key[2] + key[3];
        vector<int> res = db[k];
        
        int cnt = res.end() - lower_bound(res.begin(), res.end(), stoi(key[4]));
        answer.push_back(cnt);
    }
    
    return answer;
}

실행 결과