2021 Kakao blind 72412 - 순위 검색(문자열 파싱, 비트마스킹, 이진탐색) c++ 풀이

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

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

- 문제에서 어려웠던 부분이 특정 조건에 해당 안되고, 모두 포함하는 조건을 어떻게 카운트할지 고민하다가, 해당 attribute가 'all'인 경우의 수를 담는 인덱스를 하나 더 만들어서 모두 카운트하는 방식으로 풀었다. 

- 개발언어, 지원직군, 경력, 소울푸드, 점수를 담는 4차원 배열의 벡터(5차원) 을 만들었다. 0번 인덱스면 'all'조건을 담는 것이고 나머지 해당 인덱스는 해쉬맵을 통해서 해당 문자열이 파싱된 인덱스에 담아진다. 

- 만들어 질 수 있는 모든 사람조건 경우의 수에 대해서 순회하도록 비트마스킹을 돌면서 해당 조건에 맞는 인덱스를 찾아 벡터에 넣어준다. 

- 그 다음에 모든 벡터들을 오름차순으로 소팅을 해주면 해당 조건에 알맞는 사람들의 점수에 대해 이분탐색으로 기준 점수 이상의 인원의 수를 구할 수 있다. 간단하게 이더레이터 연산으로 (iterator)end() - (iterator)특정 점수의 하한 = (int)특정 점수 이상의 인원 수가 나온다

#include <algorithm>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<string, int> umap{
    {"-", 0},
    {"cpp", 1},
    {"java", 2},
    {"python", 3},
    {"backend", 1},
    {"frontend", 2},
    {"junior", 1},
    {"senior", 2},
    {"chicken", 1},
    {"pizza", 2}};
vector<int> parsedInfo[4][3][3][3];

vector<int> solution(vector<string> info, vector<string> query) {
    string lang, pos, exp, food, etc;
    int score;

    for (string& str : info) {
        stringstream ss(str);
        ss >> lang >> pos >> exp >> food >> score;
        vector<int> v = {umap[lang], umap[pos], umap[exp], umap[food]};
        for (int i = 0; i < (1 << 4); ++i) {
            int idx[4] = {0};
            for (int j = 0; j < 4; ++j) {
                if (i & (1 << j)) {
                    idx[j] = v[j];
                }
            }

            parsedInfo[idx[0]][idx[1]][idx[2]][idx[3]].push_back(score);
        }
    }

    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                for (int l = 0; l < 3; ++l) {
                    sort(parsedInfo[i][j][k][l].begin(), parsedInfo[i][j][k][l].end());
                }
            }
        }
    }

    vector<int> ans;
    for (string& q : query) {
        stringstream ss(q);
        ss >> lang >> etc >> pos >> etc >> exp >> etc >> food >> score;

        vector<int>& v = parsedInfo[umap[lang]][umap[pos]][umap[exp]][umap[food]];
        int num = v.end() - lower_bound(v.begin(), v.end(), score);
        ans.push_back(num);
    }

    return ans;
}