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

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

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

문제 유형

Map, 이분 탐색(Binary Search)

 

2021 카카오 블라인드 코딩 테스트의 3번 문제이다.

만약 java를 사용한 backend 직군의 junior 경력인 사람의 소울푸드가 chicken이고 점수는 150점인 경우, 해당하는 조건은 다음과 같다.

java backend junior chicken 150

위 조건을 포함할 수 있는 모든 경우를 나열해 보면 다음과 같다.

- backend junior chicken 150

java - junior chicken 150

java backend - chicken 150

java backend junior - 150

- - junior chicken 150

...

- - - - 150

따라서 각 지원자의 정보를 위와 같이 가능한 모든 케이스로 분해해, 각 케이스에 지원자의 점수를 넣는다.

이 풀이에서는 map<string, vector<int>>을 이용했는데, map의 key를 하나의 문자열로 만들어 지원자의 점수를 추가했다.

위의 예시에서는 "javabackendjuniorchicken" key에 해당하는 vector에 150을 추가, "-backendjuniorchicken" key에 해당하는 vector에도 150을 추가, "--juniorchicken" key에도 추가, ...하는 식이다.

이렇게 모든 지원자에 대해 모든 케이스들을 저장한 후에는, 쿼리들을 위와 같은 하나의 문자열로 동일하게 구성하여 해당하는 vector 내에서 쿼리의 점수보다 높은 지원자의 수만 검색하면 된다.

지원자의 수가 최대 5만 명, 쿼리의 수가 최대 10만개이므로 선형 탐색이 아닌 이분 탐색으로 정답을 찾는다. (lower_bound 이용 시 각 vector를 정렬해야 함에 주의하자.)

 

[코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
 
using namespace std;
typedef pair<int, int> p;
 
map<string, vector<int>> dict;
 
void make_comb(vector<string> item){
    //bit를 이용해 가능한 모든 조합을 만듬 (0000 ~ 1111)
    for(int state = 0; state <= 15; state++){
        string key = "";
        for(int i = 0; i < 4; i++){
            if(state & (1 << i)) key += item[i];
            else key += "-";
        }
        int score = atoi(item[4].c_str());
        dict[key].push_back(score);
    }
}
 
int get_query(vector<string> item){
    string key = "";
    int score = atoi(item[4].c_str());
    for(int i = 0; i < 4; i++) key += item[i];
    
    vector<int> list = dict[key];
    
    int idx = lower_bound(list.begin(), list.end(), score) - list.begin();
    return dict[key].size() - idx;
}
 
vector<string> prev_action(string input){
    int lastidx = 0;
    vector<string> ret;
    for(int i = 0; i < input.size(); i++){
        if(input[i] == ' ' || i == input.size() - 1){
            //공백 발견시 끊는다.
            int to = i - lastidx;
            if(i == input.size() - 1) to += 1;
            string temp = input.substr(lastidx, to);
            lastidx = i + 1;
            if(temp == "and") continue;
            ret.push_back(temp);
        }
    }
    return ret;
}
 
vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    for(int i = 0; i < info.size(); i++) make_comb(prev_action(info[i]));
    map<string, vector<int>>::iterator iter;
    for(iter = dict.begin(); iter != dict.end(); iter++){
        sort(iter->second.begin(), iter->second.end());
    }
    
    for(int i = 0; i < query.size(); i++){
        int res = get_query(prev_action(query[i]));
        answer.push_back(res);
    }
    
    return answer;
}