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

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/72412

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

 

작년 2021년 하반기에 진행되었던 (그리고 제가 떨어진) 2021 Kakao Blind Recruitment의 3번 문제입니다.

제 기억에는 이 문제가 없는데, 아마 2번 문제까지 풀고 다른 문제를 뒤적이지 않았나 싶네요.

 

카카오 기술블로그의 문제 해설에 따르면, 정확성 정답률 44.07%, 효율성 4.49%라고 합니다.

 

제가 떠올린 방법은 unordered map (hashmap)을 이용하는 것입니다.

unordered map은 값의 삽입 및 조회에 평균 O(1)의 시간복잡도를 가지므로, 시간복잡도 문제를 해결할 수 있을 것이라고 판단했습니다.

 

그래서... 좀 지저분하지만 4중 unordered_map + 점수를 담기 위한 vector를 하여 아래와 같이 db를 선언하였습니다.

unordered_map<string,
    unordered_map<string,
    unordered_map<string,
    unordered_map<string,
    vector<int> > > > > db;

주어진 info 내용을 파싱한 후에 db의 알맞은 위치에 넣게 됩니다.

총 경우의 수는 3 * 2 * 2 * 2 = 24가지입니다.

 

다음으로는 주어진 query에 맞는 값을 조회하게 됩니다.

조회를 위해서는 쿼리문을 완성해야 하는데, 조건에 '-' 가 들어오는 경우, 모든 가능한 경우를 포함하여 찾게 됩니다.

저는 이를 위해 dfs를 이용하여 쿼리를 작성하였습니다.

int dfs (vector<string> &queryIn, vector<string> queryOut) {
    // 쿼리를 완성하였다.
    int ans = 0;
    if (queryOut.size() == 5) {
        ans += moreThan(db[queryOut[0]][queryOut[1]][queryOut[2]][queryOut[3]], stoi(queryIn[4]));
    }
    else {
        int nextIter = queryOut.size();
        if (queryIn[nextIter] == "-") {
            for (auto &next : vals[nextIter]) {
                queryOut.push_back(next);
                ans += dfs(queryIn, queryOut);
                queryOut.pop_back();
            }
        }
        else {
            queryOut.push_back(queryIn[nextIter]);
            ans += dfs(queryIn, queryOut);
        }
    }
    return ans;
}

이 dfs는 쿼리를 완성시키고 나면 moreThan을 호출하여 주어진 기준 점수 이상의 점수를 기록한 사람의 수를 세는데, 최악의 경우 쿼리가 '- and - and - and - 100' 와 같이, 조건이 전부 -로 주어지는 경우, 문제의 경우의 수만큼 호출하게 됩니다.

즉 24번 호출하게 되는데, 쿼리는 최대 10만 개까지 주어지므로, 10만 * 24 = 240만으로, 감당할 수 있는 숫자입니다.

 

기준점 이상의 사람의 수를 세는 함수 moreThan은 lower_bound를 이용하여 쉽게 값을 구합니다.

 

전체적인 함수의 흐름은 아래와 같습니다.

 

함수명은 형광펜으로 표시하였습니다.

 

코드 링크: GitHub, 시간 초과 코드 (GitHub)

// 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/72412
#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <algorithm>

using namespace std;

unordered_map<string, unordered_map<string, unordered_map<string, unordered_map<string, vector<int> > > > > db;
vector<vector<string> > vals = {{"cpp", "java", "python"}, {"backend", "frontend"}, {"junior", "senior"}, {"chicken", "pizza"}};
vector<int> answer;

void dbInit() {
    vector<int> score;
    
    unordered_map<string, vector<int> > food;
    food.insert({"chicken", score});
    food.insert({"pizza", score});
    
    unordered_map<string, unordered_map<string, vector<int> > > exp;
    exp.insert({"junior", food});
    exp.insert({"senior", food});
    
    unordered_map<string, unordered_map<string, unordered_map<string, vector<int> > > > group;
    group.insert({"backend", exp});
    group.insert({"frontend", exp});
    
    db.insert({"cpp", group});
    db.insert({"java", group});
    db.insert({"python", group});

    return;
}

void dbSort() {
    for (int a = 0; a < vals[0].size(); a++) {
        for (int b = 0; b < vals[1].size(); b++) {
            for (int c = 0; c < vals[2].size(); c++) {
                for (int d = 0; d < vals[3].size(); d++) {
                    sort(db[vals[0][a]][vals[1][b]][vals[2][c]][vals[3][d]].begin(), db[vals[0][a]][vals[1][b]][vals[2][c]][vals[3][d]].end());
                }
            }
        }
    }
}

//score 이상 원소 수를 센다
int moreThan(vector<int> &nums, int score) {
    
    if (nums.size() == 0) {
        return 0;
    }
    
    int pos = lower_bound(nums.begin(), nums.end(), score) - nums.begin();
    return nums.size() - pos;
}

int dfs (vector<string> &queryIn, vector<string> queryOut) {
    // 쿼리를 완성하였다.
    int ans = 0;
    if (queryOut.size() == 5) {
        ans += moreThan(db[queryOut[0]][queryOut[1]][queryOut[2]][queryOut[3]], stoi(queryIn[4]));
    }
    else {
        int nextIter = queryOut.size();
        if (queryIn[nextIter] == "-") {
            for (auto &next : vals[nextIter]) {
                queryOut.push_back(next);
                ans += dfs(queryIn, queryOut);
                queryOut.pop_back();
            }
        }
        else {
            queryOut.push_back(queryIn[nextIter]);
            ans += dfs(queryIn, queryOut);
        }
    }
    return ans;
}

void queryInsert(vector<string> &result) {
    db[result[0]][result[1]][result[2]][result[3]].push_back(stoi(result[4]));
}

void findUser(vector<string> &result) {
    vector<string> queryOut;
    int score = dfs(result, queryOut);
    answer.push_back(score);
}

vector<int> solution(vector<string> info, vector<string> query) {
    
    dbInit();
    
    // info를 파싱하여 db에 삽입
    for (auto &next : info) {
        istringstream ss(next);
        string buffer;
        vector<string> result;
        
        while(getline(ss, buffer, ' ')) {
            result.push_back(buffer);
        }
        
        queryInsert(result);
    }
    
    // 각 점수 정렬
    dbSort();
    
    // 각 조건에 맞게 검색
    for (auto &next : query) {
        istringstream ss(next);
        string buffer;
        vector<string> result;
        
        while(getline(ss, buffer, ' ')) {
            if (buffer != "and")
                result.push_back(buffer);
        }
        
        findUser(result);
    }
    
    return answer;
}

위의 링크로 달아둔 시간 초과가 발생하는 코드는 정확도 100%, 효율성 0%를 받은 코드입니다.

차이점은 moreThan에서 vector nums를 정렬했다는 점인데, 이 경우 sort가 최대 240만 번 돌아갈 수 있으므로...

시간 초과가 나게 됩니다.

따라서 쿼리 수행 전에 일괄적으로 정렬하는 함수 dbSort를 작성하여 사용하였습니다.

 

Level 2인데... Level 2같지 않은 문제였습니다.

늘 느끼지만 카카오 공채에서 나왔던 문제들은 프로그래머스의 같은 난이도의 다른 문제들보다 훨씬 어려운 것 같습니다.

지난 코테에서 3~3.5솔? 정도면 1차 코테 합격이었다고 들은 것 같은데 역시 쉽지 않네요.

 

그래도 제 힘으로 풀어내서 뿌듯하네요 ㅎㅎ