programmers Level 2 순위 검색

문제

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

걸린 시간

01 : 14 : 48 실패

풀이

C++

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

bool compare(int a, int b){
    return a < b;
}

vector<string> split(string input, char delimiter){
    vector<string> ret;
    istringstream iss(input);
    string token;
    while(getline(iss, token, delimiter))
        ret.push_back(token);
    return ret;
}

vector<int> solution(vector<string> info, vector<string> query) {
    map<string, int> m;
    m["cpp"] = 0;
    m["java"] = 1;
    m["python"] = 2;
    m["backend"] = 0;
    m["frontend"] = 1;
    m["junior"] = 0;
    m["senior"] = 1;
    m["chicken"] = 0;
    m["pizza"] = 1;
    vector<int> answer;
    vector<int> db[3][2][2][2];
    for(string i : info){
        vector<string> s = split(i, ' ');
        db
            [m[s[0]]]
            [m[s[1]]]
            [m[s[2]]]
            [m[s[3]]].push_back(stoi(s[4]));
    }
    for(int l = 0; l < 3; l++){
        for(int j = 0; j < 2; j++){
            for(int c = 0; c < 2; c++){
                for(int f = 0; f < 2; f++){
                    sort(db[l][j][c][f].begin(), db[l][j][c][f].end(), compare);
                }
            }
        }
    }
    for(string i : query){
        vector<string> s = split(i, ' ');
        int ls, le, js, je, cs, ce, fs, fe;
        if(s[0] == "-") ls = 0, le = 2;
        else ls = le = m[s[0]];
        if(s[2] == "-") js = 0, je = 1;
        else js = je = m[s[2]];
        if(s[4] == "-") cs = 0, ce = 1;
        else cs = ce = m[s[4]];
        if(s[6] == "-") fs = 0, fe = 1;
        else fs = fe = m[s[6]];
        int cnt = 0;
        for(int l = ls; l <= le; l++){
            for(int j = js; j <= je; j++){
                for(int c = cs; c <= ce; c++){
                    for(int f = fs; f <= fe; f++){
                        vector<int> &point = db[l][j][c][f];
                        auto iter = lower_bound(point.begin(), point.end(), stoi(s[7]));
                        if(iter == point.end()) continue;
                        cnt += point.size()-(iter-point.begin());
                    }
                }
            }
        }
        answer.push_back(cnt);
    }
    return answer;
}

지원자가 입력한 4가지 항목의 문자열을 인덱스화 할 생각을 하지 못해 - 입력 시 어떤 식으로 6,561(3^2^2^2) 가지의 분류를 확인해야할 지 몰랐다.

점수 배열을 미리 오름차순 정렬해두고 이분 탐색을 이용한다면, X 점 이상의 지원자의 수를 구하는 연산을 상수 시간으로 줄일 수 있었다.

새롭게 알게 된 지식이 두 가지가 있다.

1. 이진 탐색을 하되, 주어진 값들 중에서 기준이 되는 값 보다 크거나 같은 값들 중 제일 작은 값의 반복자를 반환하는 lower_bound 함수
2. 반복자간 사칙 연산을 수행하면 정수형의 결과값을 가짐

JavaScript

function solution(info, query) {
    const answer = [];
    const lower_bound = (li, k) => {
        let m = 0;
        let l = 0;
        let r = li.length-1;
        while(l <= r){
            m = Math.floor((l+r)/2);
            if(k <= li[m]) r = m-1;
            else l = m+1;
        }
        return k > li[m] ? m+1 : m;
    }
    const n_array = (li, i, n, el) => {
        if(i === li.length-1){
            if(typeof el === 'object'){
                const tmp = Array(li[i]);
                for(let i = 0; i < li[i]; i++)
                    tmp[i] = JSON.parse(JSON.stringify(el))
                return tmp;
            }
            else return Array(li[i]).fill(el);
        }
        else return Array.from(Array(li[i]), () => n_array(li, i+1, n, el))
    }
    const db = n_array([3, 2, 2, 2], 0, 4, []);
    const d = {};
    d.cpp = d.backend = d.junior = d.chicken = 0;
    d.java = d.frontend = d.senior = d.pizza = 1;
    d.python = 2;
    for(let i of info){
        let t = i.split(' ');
        db
        [d[t[0]]]
        [d[t[1]]]
        [d[t[2]]]
        [d[t[3]]].push(parseInt(t[4]));
    }
    for(let i = 0; i < 3; i++){
        for(let j = 0; j < 2; j++){
            for(let k = 0; k < 2; k++){
                for(let l = 0; l < 2; l++){
                    li = db[i][j][k][l];
                    li.sort((a, b) => {
                        if(a > b) return 1;
                        else return -1;
                    });
                }
            }
        }
    }
    for(let q of query){
        let t = q.split(/and|\s/).filter(el => el !== '');
        let cnt = 0;
        // < > 가 || 보다 우선순위가 높다.
        for(let i = (d[t[0]] || 0); i < (d[t[0]]+1 || 3); i++){
            for(let j = (d[t[1]] || 0); j < (d[t[1]]+1 || 2); j++){
                for(let k = (d[t[2]] || 0); k < (d[t[2]]+1 || 2); k++){
                    for(let l = (d[t[3]] || 0); l < (d[t[3]]+1 || 2); l++){
                        let li = db[i][j][k][l];
                        cnt += li.length - lower_bound(li, parseInt(t[4]));
                    }
                }
            }
        }
        answer.push(cnt)
    }
    return answer;
}

1. 4가지 항목의 요소들을 인덱스화해서 지원자 점수를 배열에 저장한다.
2. 효율성 테스트를 통과하기 위해 배열을 정렬한 후 이진탐색을 이용해 X 점 이상의 지원자 수를 센다.

중복된 값이 존재하는 지원자의 점수 오름차순 배열에서 X 점 보다 크거나 같은 인덱스를 찾아야 하므로, 하한선 lower bound 이진 탐색 알고리즘을 구현해 사용하면 된다.

기억해야 할 것

• 정렬 함수

javascript array 객체 sort 메소드의 비교함수

c++ algorithm 라이브러리 sort 함수의 비교함수

c++ 은 bool 값에 따라 앞의 요소 a 가 뒤의 요소 b 보다 먼저 이동한다고 표현되어 있는데, a 가 b 의 앞으로 온다는 이야기인 것 같다.
즉, c++ 의 true 가 javascript 의 -1 과 같고, false 가 1 과 같다.

• 연산자 우선순위

문제에서 - 의 처리를 위해 or 을 의미하는 || 를 for 문 안에 사용했지만, or 기호는 조건식의 비교문자 <, > 보다 연산자 우선순위가 낮아 의도한대로 값이 대입되지 않았다. 괄호를 사용해서 우선순위를 바꾸어주어야 한다.