순위검색

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

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

function solution(info, query) {
    const answer = [];
    const infoMap = {};
    
    // info를 obj에 저장해서 처리
    
    const combination = (array, score, start) => {
        const key = array.join("");
        if (infoMap[key]) infoMap[key].push(score);
        else infoMap[key] = [score];
        for (let i = start; i < array.length; i++) {
            const temp = [...array];
            temp[i] = "-";
            combination(temp, score, i + 1);
        }
    }
    
    for (const e of info) {
        const splited = e.split(" ");
        const score = +splited.pop();
        combination(splited, score, 0);
    }
    
    for (const key in infoMap) {
        infoMap[key] = infoMap[key].sort((a, b) => a - b);
    }
    
    for (const e of query) {
        const splitted = e.replace(/ and /g, " ").split(" ");
        const score = +splitted.pop();
        const key = splitted.join("");
        const arr = infoMap[key];
        if (arr) {
            let start = 0;
            let end = arr.length;
            while (start < end) {
                const mid = Math.floor((start + end) / 2);
                if (arr[mid] >= score) end = mid;
                else if (arr[mid] < score) start = mid + 1;
            }
            const result = arr.length - start;
            answer.push(result);
        } else answer.push(0);
    }
    return answer;
}