[Programmers] 순위 검색

문제를 보고 처음 떠올린 방법은, 점수순으로 정보를 나열하고 정렬해서, 기준점수를 만족할 때까지만 조건을 확인하고 정답을 증가시키는 방법이었다.
info를 입력받을 때 반복문의 i값을 이용해서 점수,i값의 pair와 key가 i value가 정보배열인 map을 생성해서, 연관되는 정보를 찾을 수 있게 했다. 이렇게 하면 점수순서로 나열하고 map에서 정보를 찾아 비교할 수 있다.
솔직히 풀면서도 효율성 안 나올 것 같았는데 역시는 역시였다.

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer(query.size(),0);
    
    string lang,part,car,food;
    int score;
    vector<pair<int,int>> rank;
    unordered_map<int,vector<string>> infoMap;
    for(int i=0; i<info.size(); i++){
        istringstream iss(info[i]);
        iss>>lang>>part>>car>>food>>score;
        rank.push_back(make_pair(score, i));
        infoMap[i] = {lang,part,car,food};
    }
    
    sort(rank.begin(), rank.end());
    reverse(rank.begin(), rank.end());
    
    
    vector<string> v1,v2(4);
    string s;
    for(int i=0; i<query.size(); i++){
        istringstream iss(query[i]);
        iss>>lang>>s>>part>>s>>car>>s>>food>>score;
        v2[0] = lang; v2[1]=part; v2[2]=car; v2[3] = food;
        
        for(int j=0; j<rank.size(); j++){
            if(rank[j].first<score) break;
            v1= infoMap[rank[j].second];
            
            int k=0;
            for(; k<v1.size(); k++){ 
                if(v2[k]!="-" && v2[k] != v1[k]) break;
            }
            
            if(k==v1.size()){
                 answer[i]++;
            }
        }
        
    }
    
    
    return answer;
}

두 번째 방법은 솔직히 살짝 생각했다가, 확신도 안 서고 좀 오바 아닌가 라는 생각에 머뭇거렸는데, 질문하기를 뒤져보다가 이게 맞는 풀이 방법이라는 것을 알게 됐다.
처음 입력받을 때 info에 대한 정보를 해당되는 집합별로 분류하는 것이다. query에 "-"가 있을 걸 고려해서 4C3, 4C2, 4C1, 4C0 인 경우에 대해 score를 저장해두고, 나중에 이용하는 방식이다.

근데, 이 방법으로도 효율성이 통과가 안됐다.
핵심적인 아이디어는 적용한 것 같은데, 왜 안되지 싶어서 계속 질문하기에 있는 효율성 팁을을 참고했다.

첫번째는 sort를 map생성후에 해주는 것이다. 효율성 테스트에 있어서는 차라리 미리 다 해버리는 게 효율적인가보다.

두번째는 binary search를 이용하는 것이었는데, 이게 인덱스 어디로 갈지 생각하는 게 머리아파서 검색해보다가 lower_bound라는 함수를 알게 됐고 사용하였다.

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer(query.size(),0);
    
    string lang,part,car,food;
    int score;
    vector<pair<int,int>> rank;
    unordered_map<string,vector<int>> infoMap;
    for(int i=0; i<info.size(); i++){
        istringstream iss(info[i]);
        iss>>lang>>part>>car>>food>>score;
        infoMap[lang+part+car+food].push_back(score);
        infoMap[part+car+food].push_back(score);
        infoMap[lang+car+food].push_back(score);
        infoMap[lang+part+food].push_back(score);
        infoMap[lang+part+car].push_back(score);
        infoMap[lang+part].push_back(score);
        infoMap[lang+car].push_back(score);
        infoMap[lang+food].push_back(score);
        infoMap[part+car].push_back(score);
        infoMap[part+food].push_back(score);
        infoMap[car+food].push_back(score);
        infoMap[lang].push_back(score);
        infoMap[part].push_back(score);
        infoMap[car].push_back(score);
        infoMap[food].push_back(score);
        infoMap[""].push_back(score);
    
    }
    
    vector<string> v(4);
    string s;
    for(int i=0; i<query.size(); i++){
        istringstream iss(query[i]);
        iss>>lang>>s>>part>>s>>car>>s>>food>>score;
        v[0] = lang; v[1]=part; v[2]=car; v[3] = food;
       
        s="";
        for(int j=0; j<v.size(); j++){
            if(v[j]!="-") s+=v[j];
        }
        
        for(int j=0; j<infoMap[s].size(); j++){
            if(infoMap[s][j]>=score) answer[i]++;
        }
    }
    
    return answer;
}

istringstream을 추천받아서 사용했는데, 확실히 타입을 바로 변환해주니까 번거로운 게 줄었다.
또 효율성을 생각해서 문제를 푸는 게 정말 머리아프고 어렵지만 중요한 과정이라고 생각했다.
다른 풀이를 보니까 처음에 map에 조합을 짜는 것도 무지성으로 하는 게 아니라 재귀를 통해서 만들던데, 다음에 그 알고리즘도 한 번 보고 이해해봐야겠다.

시간도 많이 썼고 다른 사람 팁을 많이 참고하긴 했지만 무려 11점이나 오르길래 뿌듯했다.