[프로그래머스][level2] 순위 검색 (C++)

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

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

 

 

[난이도] level2
[유형] 이분탐색

[풀이]
당연히 그냥 구현 문제일줄 알았는데 info의 범위가 50000 query의 범위가 100000이나 되기 때문에
쿼리마다 모든 info를 확인하는 O(query*info)의 시간복잡도로는 효율성 테스트 통과가 불가능합니다.

지원자의 4가지 항목을 4자리 수로 변환해주는 Hashing과
어떤 점수를 넘는 지원자를 찾기 위한 binary search를 사용해주면 문제를 해결할 수 있습니다.

1) 아래와 같이 4가지 항목으로 숫자로 변환해주는 map 테이블을 만듭니다.
cpp, java, python => 1,2,3
backend, frontend => 1,2
junior, senior => 1,2
chicken, pizza => 1,2

2) 지원자의 정보 string을 분리하여 hash값을 만든 뒤 map> 타입의 map에
형태로 저장합니다. ex) mp["1111"].push_back(150)
그 뒤 map을 순회하면서 vector들을 정렬해줍니다. (binary search를 사용하기 위함입니다.)

3) query를 순회하면서 string을 쪼개서 만들 수 있는 모든 hash를 만들어줍니다.
저는 vector 4개를 선언하여 "-" 가 아닌 경우에는 그에 맞는 string의 변환값을 넣어주었고,
"-"인 경우에는 1,2 (언어의 경우 3까지) 모두 되므로 모두 vector에 넣어준 뒤
4중 for문을 돌려서 만들 수 있는 모든 hash를 만들어주었습니다.
query가 -,-,-,- 이어도 최대 3x2x2x2=24개 이기때문에 많은 시간이 들지 않습니다.

각 2)에서 저장한 hash key에 맞는 점수들이 저장되어있는 vector를 map에서 가져와
binary search를 통해 조건을 만족하는 가장 적은 점수의 지원자의 iterator를 가져옵니다.
mp[key].end()-it를 통해 조건을 만족하는 모든 지원자를 구할 수 있습니다.
이 값을 cnt 변수에 카운트해주면 최종 cnt 값이 현재 query의 정답입니다.

 

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

map<string,string> table;

vector<string> split(string s,string splitter){
    vector<string> ret;
    s+=splitter;
    int idx;
    while((idx=s.find(splitter)) != string::npos){
        string tmp = s.substr(0,idx);
        ret.push_back(tmp);
        //cout << tmp << '\n';
        s=s.substr(idx+splitter.size());
    }    
    return ret;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;

    table["cpp"]="1",table["java"]="2",table["python"]="3";
    table["backend"]="1",table["frontend"]="2";
    table["junior"]="1",table["senior"]="2";
    table["chicken"]="1",table["pizza"]="2";

    map<string,vector<int>> mp;
    for(auto s : info) {
        auto v = split(s," ");
        string hash;
        for(int i=0;i<v.size()-1;i++){
            hash+=table[v[i]];
        }
        mp[hash].push_back(stoi(v.back()));
    }
    for(auto& p : mp){
        sort(p.second.begin(),p.second.end());
    }

    int qnum=0;
    for(auto q : query){
        vector<string> sq = split(q," and ");
        vector<string> b = split(sq.back()," ");
        sq.pop_back();
        sq.insert(sq.end(),b.begin(),b.end());

        vector<string> v[4];

        for(int i=0;i<4;i++){
            if(sq[i]!="-") v[i] = {table[sq[i]]};
            else {
                v[i] = {"1","2"};
                if(i==0) v[i].push_back("3");
            }
        }

        int cnt=0;
        for(auto c1 : v[0]){
            for(auto c2 : v[1]){
                for(auto c3 : v[2]){
                    for(auto c4: v[3]){
                        string key = c1+c2+c3+c4;
                        int target=stoi(sq[4]);
                        auto it = lower_bound(mp[key].begin(),mp[key].end(),target);
                        cnt+=mp[key].end()-it;
                    }
                }
            }
        }
        answer.push_back(cnt);

    }
    return answer;
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/순위 검색.cpp