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

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define long long size_t
using namespace std;

map<string, vector<int>> scores;

void storeScore(vector<vector<string>> &tmp, int score) {
    string c1, c2, c3, c4;
    
    for (int i=0; i<2; i++) {
        c1 = tmp[0][i];
        for (int j=0; j<2; j++) {
            c2 = tmp[1][j];
            for (int k=0; k<2; k++) {
                c3 = tmp[2][k];
                for (int l=0; l<2; l++) {
                    c4 = tmp[3][l];
                    scores[c1 + c2 + c3 + c4].push_back(score);
                }
            }
        }
    }
}

vector<int> solution(vector<string> info, vector<string> query){
    vector<int> answer;
    vector<vector<string>> tmp(4, vector<string>(2,"-"));
    for(int i=0; i<info.size(); i++){
        string s;
        int idx = 0, score = 0;
        stringstream ss(info[i]);
        while(ss>>s){
            if(idx<4) tmp[idx++][0] = s;
            else score = stoi(s); // 마지막은 숫자니까 정수로 바꿔서 score에 저장
        }
        storeScore(tmp, score);
    }
    // 점수 오름차순 정렬
    for (auto it:scores){
        sort(scores[it.first].begin(), scores[it.first].end());
    }
    for(string q: query){
        string s, key = "";
        int idx = 0, score = 0;
        stringstream ss(q);
        while(ss>>s){
            if(s=="and") continue;
            if(idx<4){
                key+=s;
                idx++;
            }else{
                score = stoi(s);
            }
        }
        auto it = lower_bound(scores[key].begin(), scores[key].end(), score);
        answer.push_back(scores[key].size() - (it-scores[key].begin()));
    }
    return answer;
}

 

참고

https://cherishvert.tistory.com/108

 

풀이

 

[코드 변수]

info[i]: 예를 들어 "java backend junior pizza 150" 이런 한 줄

stringstream ss(info[i]);는 문자열을 공백 기준으로 자른다.

idx: 속성 4개를 순서대로 넣기 위한 인덱스

while(ss>>s)를 통해 처음 4개는 tmp[0][0], tmp[1][0], ... 에 저장됨

 

→ storeScore(tmp, score)로 넘겨서 "java-backend-junior-pizza" 포함
모든 조합(java-backend-junior-pizza, java-backend--pizza, ----, ...)을
key로 만들고 score를 벡터에 저장한다.

 

[query 처리]

:query 하나씩 꺼내서 → key로 바꾸고 → scores[key]에서 점수가 기준 이상인 사람 수를 찾아 → answer에 넣는다.

q = "java and backend and junior and pizza 100";

→ key = "javabackendjuniorpizza"

→ score = 100

 

scores[key]는 점수 리스트 (예: [80, 150, 210])

lower_bound(...): score 이상인 첫 번째 위치 iterator를 반환

answer.push_back(scores[key].size() - (it - scores[key].begin()));

<예시>

scores[key] = [50, 70, 100, 150]

score = 100일 때 lower_bound(...)는 it가 3번째 위치를 가리킴

전체 - 앞에 있는 것 수 → 4 - 2 = 2