[c++] 순위 검색

---

2021 KAKAO BLIND RECURITMENT

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

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

---

map과 이분 탐색의 환장적인 콜라보!

• 나는 어째서인지 조건들을 무조건 분리해서 map에 다 따로 저장하려고 했는데 조건 전체를 하나의 문자열로 해서 key로 저장하는건 생각 못했다.
• 주어진 조건을 만족할 수 있는 모든 경우의 수를 만들어보는 것도 역시 생각 못했다.

이틀을 고민하다가 결국 해설지를 보고 풀 수 있었다.

 

1. map을 사용한 자료구조

"java backend junior pizza 150"

위와 같은 정보를 가진 지원자는 쿼리 조건에 -가 올 수 있는 것을 고려해서 총 16가지의 조건에 부합하는 사람이다.

이 조건들을 key로 하고 점수를 value로 가지는 map을 만들 수 있다.

이렇게 되면 map에는 "javabackendjuniorpizza"를 key로 가지고 150을 value로 가진 요소가 있을 것이다.

16가지의 key를 만드는 법은 다양한데 나는 조합으로 만들었다.

이 때, 같은 조건을 가진 사람들이 여러 명일 수 있기 때문에 value를 vector<int>로 했다.

 

2. 이분 탐색

지원자의 정보 및 쿼리의 최대 갯수를 고려했을 때, 점수를 브루트포스로 하나씩 비교하면 5만 * 10만 = 50억의 시간이 걸리기 때문에 다른 방법을 써야 한다.

자료의 갯수가 많을 때 가장 적절한 방법은 이분 탐색이다.

이 때, 특정 점수를 가진 사람이 처음으로 나오는 인덱스를 알면 몇 명인지 알 수 있기 때문에 lowerbound를 찾으면 된다.

이분 탐색은 정렬된 자료에서 사용 가능하기 때문에 lowerbound를 찾기 전에 vector를 정렬해야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <algorithm>

using namespace std;

map<string, vector<int>> list;

void make_comb(vector<string> splitted, string s, int idx, int depth) {
    if (depth == 4) {
        list[s].push_back(stoi(splitted[4]));
        return;
    }
    make_comb(splitted, s + splitted[idx], idx + 1, depth + 1);
    make_comb(splitted, s + "-", idx + 1, depth + 1);
}

vector<string> split_info(string info) {
    vector<string> splitted;
    stringstream input(info);
    string temp;

    while (getline(input, temp, ' ')) {
        splitted.push_back(temp);
    }

    return splitted;
}

pair<string, int> split_query(string query) {
    string splitted = "";
    stringstream input(query);
    string temp;

    for (int i = 0; i < 7; i++) {
        getline(input, temp, ' ');
        if (temp.compare("and") == 0) continue;
        splitted += temp;
    }
    getline(input, temp, ' ');

    pair<string, int> p;
    p.first = splitted;
    p.second = stoi(temp);

    return p;
}

vector<int> solution(vector<string> infos, vector<string> queries) {
    vector<int> answer;

    for (string info : infos) {
        vector<string> splitted = split_info(info);
        make_comb(splitted, "", 0, 0);
    }

    for (auto l : list) {
        sort(l.second.begin(), l.second.end());
        list[l.first] = l.second;
    }

    for (string query : queries) {
        pair<string, int> p = split_query(query);
        // 해당 조건을 가진 지원자가 없을 때
        if (list.find(p.first) == list.end()) {
            answer.push_back(0);
        }
        // 해당 조건을 가진 지원자가 있을 때
        else {
            vector<int> score = list[p.first];
            int idx = lower_bound(score.begin(), score.end(), p.second) - score.begin();
            // 주어진 점수 이상을 가진 지원자가 있을 때
            if (idx < (int)score.size()) {
                answer.push_back((int)score.size() - idx);
            }
            else {
                answer.push_back(0);
            }
        }
    }

    return answer;
}

int main() {
    vector<string> info = {
        "java backend junior pizza 150",
        "python frontend senior chicken 210",
        "python frontend senior chicken 150",
        "cpp backend senior pizza 260",
        "java backend junior chicken 80",
        "python backend senior chicken 50"
    };

    vector<string> query = {
        "java and backend and junior and pizza 100",
        "python and frontend and senior and chicken 200",
        "cpp and - and senior and pizza 250",
        "- and backend and senior and - 150",
        "- and - and - and chicken 100",
        "- and - and - and - 150"
    };

    vector<int> answer = solution(info, query);
    for (int i : answer)
        cout << i << '\n';
}

 

참고) 만약 효율성 검사를 통과하지 못했다면 쿼리를 분리하는 반복문에서 vector를 정렬하고 있지 않은지 봐야한다.

그렇다면 지원자의 정보로 map을 다 만든 후에 순회하면서 vector를 정렬하면 효율성 테스트도 통과할 수 있다.