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

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

프로그래머스

 

문제 분석

주어진 문제는 채용 지원자들의 정보를 바탕으로, 특정 조건을 만족하는 지원자가 몇 명인지 찾는 문제입니다. 지원자 정보는 info 배열로 주어지며, query 배열은 각 개발팀이 궁금한 조건을 포함합니다. 각 info 항목은 "개발언어 직군 경력 소울푸드 점수"의 형식으로 구성되고, 각 query 항목은 "개발언어 and 직군 and 경력 and 소울푸드 점수" 형식입니다.

각 query에 대해 조건을 만족하는 지원자가 몇 명인지 찾아야 합니다.

접근법

1. 데이터 분해 및 저장: 각 지원자의 정보를 파싱하고, 이를 저장하는 방식이 필요합니다. 다양한 조건이 있을 수 있으므로, 각 조건을 쉽게 탐색할 수 있는 자료구조를 사용하는 것이 효율적입니다.
2. 비트마스킹: 각 정보에 대한 조건을 조합하는 방법으로 비트마스킹을 사용하여 가능한 모든 조합을 미리 계산해두고, 나중에 query를 빠르게 처리할 수 있습니다.
3. 이진 탐색을 통한 최적화: 점수에 대한 조건이 주어졌을 때, 조건을 만족하는 점수만을 빠르게 찾기 위해 이진 탐색을 사용합니다. 각 조합에 대해 미리 점수를 정렬해둔 후, lower_bound 함수를 사용하여 빠르게 점수를 찾을 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

vector<string> data_parse(string data){
    vector<string> ret;
    string tmp = "";

    for(auto d : data){
        if(d == ' '){
            if(tmp != "and") ret.push_back(tmp); // 'and'는 무시
            tmp = "";
        } else {
            tmp += d;
        }
    }
    ret.push_back(tmp); // 마지막 단어 추가
    return ret;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    unordered_map<string, vector<int>> m;

    // info 데이터를 조합하여 저장
    for(auto data : info){
        vector<string> key = data_parse(data); // 데이터를 파싱
        int num = stoi(key[4]); // 점수 추출

        // 비트마스크로 가능한 모든 조합 생성 (16개)
        for(int i = 0; i < 16; i++){
            string tmp = "";
            for(int j = 0; j < 4; j++){
                if(i & (1 << j)){ // 비트가 1이면 해당 조건 선택
                    tmp += key[j];
                } else { // 비트가 0이면 선택하지 않음
                    tmp += "-";
                }
            }
            m[tmp].push_back(num); // 해당 조합에 점수 저장
        }
    }

    // 각 조합의 점수를 정렬
    for(auto& it : m){
        std::sort(it.second.begin(), it.second.end());
    }

    // query 처리
    for(auto q : query){
        vector<string> key = data_parse(q); // query 파싱
        string s = key[0] + key[1] + key[2] + key[3]; // 조건 조합
        int num = stoi(key[4]); // 점수 추출

        // 이진 탐색으로 조건을 만족하는 점수 개수 찾기
        int cnt = m[s].end() - lower_bound(m[s].begin(), m[s].end(), num);
        answer.push_back(cnt);
    }

    return answer;
}

비트 마스킹 원리

for(int i = 0; i < 16; i++)는 비트마스크를 사용하여 4개의 조건(개발언어, 직군, 경력, 소울푸드)에 대해 가능한 모든 조합을 탐색하는 부분입니다. 각 조건은 선택하거나 선택하지 않을 수 있기 때문에, 총 16개의 경우의 수가 생깁니다. 이는 4개의 이진수 자리(2^4 = 16)로 표현될 수 있습니다.

총 4가지의 조건이 있으며, 각 조건마다 선택한다 (1) , 하지 않는다(0) 의 상태를 가집니다,

즉, 2^4 = 16 가지의 조합이 가능합니다.

예를 들어 0000 은 어느 조건도 선택하지 않는경우, 1111 은 모든 조건을 선택하는 경우 입니다.

for(int i = 0; i < 16; i++){
    string tmp = "";
    for(int j = 0; j < 4; j++){
        if(i & (1 << j)){ // 비트가 1이면 해당 조건 선택
            tmp += key[j];
        } else { // 비트가 0이면 선택하지 않음
            tmp += "-";
        }
    }
    m[tmp].push_back(num); // 해당 조합에 점수 저장
}

위 코드에서 i & (1 << j) 를 통해 i 의 j 번째 비트가 1인지 확인 후, 1이라면 key 에 저장된 j 값, 0 이라면 - 를 저장합니다.

예시: i가 0부터 15까지 변하는 과정

i (10진수) i (2진수) 선택 여부 (i & (1 << j))

0	0000	모든 조건을 선택하지 않음
1	0001	첫 번째 조건만 선택
2	0010	두 번째 조건만 선택
3	0011	첫 번째, 두 번째 조건 선택
4	0100	세 번째 조건만 선택
5	0101	첫 번째, 세 번째 조건 선택
6	0110	두 번째, 세 번째 조건 선택
7	0111	첫 번째, 두 번째, 세 번째 조건 선택
...	...	...
15	1111	모든 조건 선택