(프로그래머스 c++ KAKAO)순위 검색

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

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

 

 

map과 이분 탐색을 이용.

map은 조건을 key, 점수를 value로 구성한다.

단, 같은 조건에 다른 점수가 존재할 수 있기 때문에 map<string, vector<int>> m 으로 선언하여 점수를 넣어주도록 한다.

 

1) info를 파싱하는데, -를 포함한 모든 경우의 수를 map에 넣어준다. query에서 나올 수 있는 조건을 모두 map에 넣어주면 된다. 2^4 = 16 이기 때문에 시간초과는 걱정하지 않아도 된다.

ex) "javabackendjuniorpizza"가 파싱 결과라면, "-backendjuniorpizza", "--juniorpizza", "---pizza"...

 

2) map을 순회하면서 점수를 오름차순으로 정렬해준다. 이분 탐색을 위해 정렬이 필요하다.

 

3) query를 파싱하여 조건을 나타내는 문자열을 얻는다.

만약 query[0]의 파싱 결과가 "--senior-" 라면 map에서 해당 문자열을 찾아 점수를 확인한다.

점수는 이분탐색을 통해 찾으며, lower_bound() 함수를 이용해 파싱한 점수보다 작지 않은 값 중 가정 첫 번째 위치를 가져온다.

그리고 answer[i]에 답을 넣어주면 된다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <sstream>

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer(query.size(), 0);
    map<string, vector<int>> m;
    
    for(int i = 0; i < info.size(); i++){
        string token;
        stringstream ss(info[i]);
        vector<vector<string>> str(4, vector<string>(2, "-"));
        int index = 0, score = 0;
        
        while(ss >> token){
            if(index < 4){
                str[index++][0] = token;    
            }
            else{
                score = stoi(token);
            }
        }
        
        for(int i = 0; i < 2; i++){
            string t1, t2, t3, t4;
            t1 = str[0][i];
            for(int j = 0; j < 2; j++){
                t2 = str[1][j];
                for(int k = 0; k < 2; k++){
                    t3 = str[2][k];
                    for(int l = 0; l < 2; l++){
                        t4 = str[3][l];
                        m[t1 + t2 + t3 + t4].push_back(score);
                    }
                }
            }
        }
    }
    
    for(auto itr = m.begin(); itr != m.end(); itr++){
        sort(itr->second.begin(), itr->second.end());
    }
    
    for(int i = 0; i < query.size(); i++){
        string str = "", token;
        stringstream ss(query[i]);
        int index = 0, score = 0;
        
        while(ss >> token){
            if(token == "and"){
                continue;
            }
            
            if(index++ < 4){
                str += token;
            }
            else{
                score = stoi(token);
            }
        }
        
        auto itr = lower_bound(m[str].begin(), m[str].end(), score);
        
        answer[i] = m[str].size() - (itr - m[str].begin());
    }
    
    return answer;
}