프로그래머스 Lv2: 순위 검색

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

얼핏 보면 brute force 로 전체를 탐색하면 되는 쉬운 문제같아 보이지만, 효율성 체크에서 fail 하기 때문에 아예 다르게 접근해야 하는 문제이다. 나도 정확성은 다 통과했으나 효율성에서 막혔다.

결국 아무리 고민해도 모르겠어서 그냥 다른 사람들의 힌트와 풀이를 보고 다시 풀었다.

문제의 핵심은 조합과 이분탐색(lowerbound)이며, for 반복을 최대한 줄여야 한다. 그러기 위해서는 최대한 for 안에 여러 작업들을 묶어서 처리한다.
예를 들어 처음에 나는 info 와 query 를 parsing 하는 for 가 각각 있었는데 이걸 다 없애야 했다.

또한 새롭게 배운 것은 객체의 key-value 쌍을 만들어 hash 처럼 사용할 때, value 를 배열로 만들고 거기에 key 가 중복되는 개체들은 그 개체의 점수만 배열에 추가하는 방식으로 중복되는 개체를 객체에 모두 담는 방법이다.
나는 처음에 Map() 객체와 JSON 으로 막 복잡하게 했었는데 위 방법은 간단하고 좋다.

function solution(info, query) {
    var answer = [];
    let map = {};

    // 조합을 만드는 함수
    function DFS(L, arr, sum, score){
        if(L===4){
            if (map[sum]) map[sum].push(score)
            else map[sum] = [score]
        }
        else {
            DFS(L+1, arr, sum + arr[L], score)
            DFS(L+1, arr, sum + '-', score)
        }
    }

    // 이분탐색 함수
    function lowerbound(scoreArr, key, score) {
    // 만약 모든 점수가 score 보다 낮으면 lt는 rt 가 되고 rt 는 처음 값을 유지한다. 
    // answer 에 넣을 때 scoreArr.length - start를 하므로
    // rt 의 초기값을 반드시 scoreArr.length 로 설정한다.
        let lt = 0, rt = scoreArr.length, mid = 0;
        while (lt < rt){
            mid = Math.floor((lt + rt)/2);
            if (scoreArr[mid] < score) lt = mid + 1;
            else rt = mid;
        }
        return rt;
    }
    
    // 1. 가능한 모든 조합 만들기
    for (let i of info){
        let arr = i.split(' ');
        let score = Number(arr.pop());
        DFS(0, arr, '', score);
    }
    
    // 2. 이분검색을 위해 점수 오름차순 정렬
    for(let key in map){
        map[key].sort((a, b) => a - b);
    }

    // 3. 이분탐색 실행
    for (let q of query){
        let key = q.replace(/ and /g, '').split(' ');
        let score = Number(key.pop());
        key = key.join('');
        let scoreArr = map[key];
        if (scoreArr) { // key 가 있으면 그 점수 배열을 이분탐색
            let start = lowerbound(scoreArr, key, score)
            answer.push(scoreArr.length - start)
        }
        else answer.push(0);
    }
    return answer;
}