프로그래머스 순위 검색 JavaScript

2023년 2월 19일

프로그래머스 순위 검색

문제 풀이

조건을 만족하는 사람 중 테스트 점수를 X점 이상 받은 사람의 수를 찾는 문제
처음에는 info를 문자열에서 객체 형태로 바꾼 배열로 만들고 query 또한 바꾼 뒤 조건에 적합한 수를 찾았다. 하지만 이 방식은 효율성 통과를 하지 못한다. 효율성 통과를 위해 이진 탐색을 이용하고 info를 객체 조건 : [점수] 형태로 저장했다. query를 정규화할 때 - 는 와일드카드로 조건의 해당 항목을 무조건 통과한다. 뒤에서 조건을 체크할 때 필요 없기에 지운다.

infoNomarlization(info): info의 값들을 조건 : [점수] 형태의 객체로 만들어 리턴, 각 조건에 [점수] 배열들은 이진 탐색을 위해 정렬

askQuestion(info_obj, query_arr, score): info_obj의 키값들을 query_arr의 조건에 맞는 값들만 필터링한 뒤(query_arr의 값들이 info_obj의 키값(= 조건)에 모두 포함되는지), info_obj[idx]에서 score를 이진 탐색한 결괏값을 자신의 길이에서 마이너스하고 가산한다. (info_obj[idx]는 정렬된 배열, 이진 탐색의 결과로 나온 인덱스 이전은 모두 score보다 작은 값 들이기 때문에 뺌)

binarySearchScore(arr, score): arr에서 score를 이진 탐색해 나온 인덱스를 리턴

solution.js

function solution(info, query) {
    const answer = [];
    const info_obj = infoNomarlization(info);
    
    query.map(query_item => query_item.split(' and '))
        .forEach(query_item => {
            const [food, score] = query_item.pop().split(' ');
            const queryNomarlization = [...query_item, food].filter(q => q !== '-');
            answer.push(askQuestion(info_obj, queryNomarlization, score));
        })
    return answer;
}

function askQuestion (info_obj, query_arr, score) {
    const infoKeys = Object.keys(info_obj);
    const cnt = infoKeys.filter(key => query_arr.every(query_arr_item => key.includes(query_arr_item)))
        .reduce((acc, idx) => {
            return acc + info_obj[idx].length - binarySearchScore(info_obj[idx], score);
        }, 0);
    return cnt;
}
function binarySearchScore(arr, score) {
    let left = 0; right = arr.length - 1; mid = 0;
    while (left <= right) {
        mid = Math.floor((left + right) / 2);
        if (arr[mid] === score) {
            return mid;
        }
        arr[mid] < score ? left = mid + 1 : right = mid - 1; 
    }
    return right + 1;
}

function infoNomarlization(info) {
    const info_obj = {};
    info.forEach((info_item) => {
        const info_arr = info_item.split(" ");
        const score = Number(info_arr.pop());
        const key = info_arr.join("");
        info_obj[key] ? info_obj[key].push(score) : info_obj[key] = [score];
    });
    for (const key in info_obj) {
        info_obj[key].sort((a, b) => a - b);
    }
    return info_obj; 
}

프로그래머스 순위 검색 JavaScript

문제 풀이

댓글