알고리즘(C++) / 프로그래머스 level 2 : 순위 검색

level 2 : 순위 검색

https://programmers.co.kr/learn/courses/30/lessons/72412?language=cpp 

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

 

코딩

//프로그래머스 순위 검색
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <algorithm>

using namespace std;

unordered_map<string, vector<int>> m;

//모든 조합 
void combination(string p[5]) {
    string s = "";
    for (int i = 0; i < (1 << 4); i++) {
        s = "";
        for (int j = 0; j < 4; j++) {
            if (i & (1 << j)) //1일때
                s += p[j];
            else  //0일때
                s += '-';
        }
        m[s].push_back(stoi(p[4])); // int형으로 변환해서 push
    }
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    //구조체 저장
    for (int i = 0; i < info.size(); i++) {
        stringstream stream(info[i]);
        string person[5];
        stream >> person[0] >> person[1] >> person[2] >> person[3] >> person[4];
        combination(person); //조합찾기
    }

    for (auto& score : m) {
        sort(score.second.begin(), score.second.end()); //score 순으로 정렬
    }

    for (int i = 0; i < query.size(); i++) {
        stringstream stream(query[i]);
        string person[5];
        string a;
        stream >> person[0] >> a >> person[1] >> a >> person[2] >> a >> person[3] >> person[4];

        vector<int> vec = m[person[0] + person[1] + person[2] + person[3]]; //find

        if (vec.size() != 0) {
            //찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
            auto it = lower_bound(vec.begin(), vec.end(), stoi(person[4])); //lower_bound 이진탐색 방법
            answer.push_back(vec.size() - (it - vec.begin()));
        }
        else {
            answer.push_back(0); //아무것도 없을 때
        }
    }

    return answer;
}

int main() {
    vector<string> info = { "java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50" };
    vector<string> query = { "java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150" };
    solution(info, query);
    return 0;
}

 

설명

• stringstream을 사용하여 언어, 직군, 경력, 소울푸드, 점수를 받아온다.
• 언어+직군+경력+소울푸드의 모든 조합을 얻어서 map에 저장한다. 이때 map의 값은 벡터로 점수로 push 한다.
• map에서 벡터를 score 오름차순으로 정렬한다.
• query에서 언어, 직군, 경력, 소울푸드, 점수를 받아온다. 
• map에서 언어+직군+경력+소울푸드 값을 vec에 받아온다.
• vec의 size가 0이 아니라면 존재한다는 의미이므로 같은 숫자가 몇 번째에서 처음 등장하는지 lower_bound함수를 이용해 찾아 push 한다. (이진 탐색) 
• size가 0이라면 0을 push한다. 

 

고찰

이번 문제는 효율성 테스트가 존재하는 문제였다. 정확성 문제는 어렵지 않게 해결할 수 있었지만 효율성 테스트에 적합하지는 않았다. 많은 시도를 해봤지만 결국 구글링을 통해서 문제를 풀었다.

효율성 문제가... 제일 어려운 거 같다...

빠른 탐색을 위해 unordered_map를 사용하였다. 하지만 문자열을 키로 사용하는 경우 문자열이 길어질수록 unordered_map이 map에 비해 더 성능이 떨어질 수 있다. 이 문제에서는 map을 사용해야 했을 거 같다.

또한 lower_bound라는 이진 탐색 방법을 새로 배울 수 있었다. 탐색에 있어 이진 탐색은 매우 빠른 탐색이므로 시간을 줄일 수 있다. 다음번에 더 자세히 설명하도록 한다.