문제 링크

---

설명

사전 지식

lower_bound

찾으려는 key 값보다 같거나 큰 숫자가 배열의 몇 번째에서 처음 등장하는지 찾는다. (단 배열 or 벡터는 오름차순 정렬되어 있어야 한다)
반환형은 iterator이다.

int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5

본론

개발팀에서 조건을 다 볼 수도 있고 몇 개만 볼 수도 있다. 따라서 list 4차원 vector 배열에 접수된 지원서의 모든 조건의 조합과 점수를 저장해두고 배열에 바로 접근해서 찾아올 수 있게 한다.

하나의 info에 대해 개발자분들이 어떤 조건을 요청할지 모르니까 미리 모든 경우에 대비하여 가능한 모든 조합을 저장을 해주고 있는 모습이다.

i가 0일때 j가 0부터 3까지 도는데 & 쉬프트 연산해서 나오는게 전부 0이기 때문에 결국 0 0 0 0을 출력한다.
i가 1일때 j가 0부터 3까지 도는데
1 & 0001 (참)
1 & 0010
1 & 0100
1 & 1000
idx[0] = arr[0];이 실행될 것이고 list에는 2 0 0 0이 저장될 것이다.

i가 3일때는
0011 & 0001 (참 -> idx[0] = arr[0])
0011 & 0010 (참 -> idx[1] = arr[1])
0011 & 0100
0011 & 1000

두번째 사진 맨 아랫 부분에 보면 i가 15일때 0, 1, 2, 3이 출력되고 있는데
1111 & 0001
1111 & 0010
1111 & 0100
1111 & 1000
4가지 경우 모두 참이기 때문이다.

그다음 lower_bound를 사용하기 위해 score를 오름차순으로 정렬하고
query에서 한 문장씩 str에 담은 후 list에서 점수를 가져온다.
즉 { 2, 1, 1, 1 }; // java backend junior chicken의 조합의 지원자가 3명이고 각각 80, 90, 95점이라면 slist[2][1][1][1] = { 80, 90, 95 }; 이렇게 저장되어 있을 것이다.

90점 이상인 사람은 lower_bound(begin, end, 90) = 1이 될 것이고 3-1=2가 될 것이다.

---

코드

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

using namespace std;

unordered_map<string, int> map;
vector<int> list[4][3][3][3];

vector<int> solution(vector<string> info, vector<string> query) {
    
    map["-"] = 0;
    map["cpp"] = 1;
    map["java"] = 2;
    map["python"] = 3;
  
    map["backend"] = 1;
    map["frontend"] = 2;
  
    map["junior"] = 1;
    map["senior"] = 2;
  
    map["chicken"] = 1;
    map["pizza"] = 2;
    
    for(auto str : info)
    {
        stringstream ss(str);
        string a, b, c, d;
        int score;
        ss >> a >> b >> c >> d >> score;

        int arr[4] = {map[a], map[b], map[c], map[d]};
        
        for(int i=0; i<(1<<4); i++) // 2^4
        {
            int idx[4] = {0};
            
            for(int j=0; j<4; j++)
                if(i & (1 << j)) 
                    idx[j] = arr[j];
                    
            list[idx[0]][idx[1]][idx[2]][idx[3]].push_back(score); 
        }
    }
    
    for(int a=0; a<4; a++)
        for(int b=0; b<3; b++)
            for(int c=0; c<3; c++)
                for(int d=0; d<3; d++)
                    sort(list[a][b][c][d].begin(), list[a][b][c][d].end());
    
    vector<int> answer;
    
    for(auto str : query)
    {
        stringstream ss(str);
        string a, b, c, d, temp; // and를 무시하기 위해 temp에 담기
        int score;
        ss >> a >> temp >> b >> temp >> c >> temp >> d >> score;
        auto& slist = list[map[a]][map[b]][map[c]][map[d]];
        
        vector<int>::iterator low = lower_bound(slist.begin(), slist.end(), score); // score에 해당하는 값중에 가장 낮은 이터레이터 가져옴
        answer.push_back(slist.end() - low);
    }
    
    return answer;
}