[프로그래머스] 순위 검색 (C++) Map을 이용한 배열화, low_bound

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

프로그래머스

풀이 방법

문제 핵심 요약

1. 4가지 조건(언어, 직군, 경력, 음식)에 대해 각각 세부 조건이 존재한다.

2. 각 조건은 ‘-’(상관없음)이라는 wildcard로 대체될 수도 있다.

3. 주어진 조건(혹은 wildcard)을 모두 만족하는 지원자들 중, 점수가 특정 기준값 이상인 지원자의 수를 빠르게 구해야 한다.

 

해결 전략

1. 모든 조건 조합에 대한 점수 저장

• 4가지 조건 각각에 -이 들어갈 수 있으므로,

 2^4 = 16 가지 경우의 수가 존재한다.

• 예를 들어, cpp backend junior pizza인 경우,

• cpp를 -로 바꿀 수도 있고

• backend를 -로 바꿀 수도 있고

• … (생략)

• 이런 식으로 총 16가지 조합에 대해 모두 점수를 저장한다.

• 이를 효율적으로 관리하기 위해 4차원 배열(score [4][3][3][3])에 점수를 삽입한다.

• 배열의 첫 번째 차원은 언어(cpp, java, python, -),

• 두 번째 차원은 직군(backend, frontend, -),

• 세 번째 차원은 경력(junior, senior, -),

• 네 번째 차원은 음식(chicken, pizza, -)을 나타낸다.

• unordered_map을 사용해 문자열(cpp, java 등)과 인덱스(1, 2, 3, 0 등)를 매핑한다.

2. 정렬을 통한 이진 탐색

• 질의에서 원하는 점수 이상의 인원을 빠르게 찾기 위해,

각 벡터(score [a][b][c][d])를score[a][b][c][d]정렬해 둔다.

• 이후 특정 점수 X 이상인 지원자 수를 구하고 싶다면,

lower_bound를 이용해 X 이상의 점수가 시작되는 인덱스를 찾고,

벡터의 끝에서 그 인덱스를 빼 인원 수를 빠르게 계산할 수 있다.

3. 쿼리 처리

• 쿼리 또한 4가지 조건(및 -) + 점수로 구성된다.

• 주어진 쿼리 문자열에 대해,

• 'and'와 같은 불필요한 단어를 제거(파싱)

• 각 조건(a, b, c, d)을 Map을 통해 인덱스로 변환

• 마지막 점수 e를 추출

• 이후 정렬된 벡터에서 e 이상인 지원자 수를 이진 탐색(lower_bound)으로 구한다.

 

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

using namespace std;

unordered_map<string, int> Map;
vector<int> score[4][3][3][3];

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    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 (int i = 0;i < info.size();i++) {
        stringstream ss(info[i]);
        string a, b, c, d;
        int e;
        ss >> a >> b >> c >> d >> e;        
        for (int j = 0;j < 16;j++) {
            int temp[4] = {Map[a], Map[b], Map[c], Map[d]};
            for (int k = 0;k < 4;k++) {
                if (j & (1 << k)) {
                    temp[k] = 0;
                }
            }
            score[temp[0]][temp[1]][temp[2]][temp[3]].push_back(e);
        }
    }    
    
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j < 3;j++) {
            for (int k = 0;k < 3;k++) {
                for (int x = 0;x < 3;x++) {
                    sort(score[i][j][k][x].begin(), score[i][j][k][x].end());
                }
            }
        }
    }
    
    for (int i = 0;i < query.size();i++) {
        string a, b, c, d, temp;
        int e;
        stringstream ss(query[i]);
        ss >> a >> temp >> b >> temp >> c >> temp >> d >> e;
        vector<int>::iterator idx = lower_bound(score[Map[a]][Map[b]][Map[c]][Map[d]].begin(), score[Map[a]][Map[b]][Map[c]][Map[d]].end(), e);
        answer.push_back(score[Map[a]][Map[b]][Map[c]][Map[d]].end() - idx);
    }
    return answer;
}