문제

이분 탐색 문제는 카테고리로 직접 명시되어 있지 않은 이상 문제에서 바로 캐치하기는 어려운 타입이다.
그럼에도 문제를 보고서는 아, 이분 탐색이구나라고 알 수 있는 힌트나 조건은 이런 것 같다.

• 데이터가 이미 정렬되어 있고, 랜덤하지 않다.
• 탐색하는 수가 매우 크다(백만 이상)

위의 문제에서는 정확히 말하자면 탐색해야하는 데이터나 정렬된 채로 주어지는 것은 아니다. 대략적으로 정해지는 답의 범위가 있고, 그 범위 내의 최솟값을 구하는 문제였다. 아무래도 이 문제가 Lv 3인 이유는 겉으로는 그리디 알고리즘으로만 풀 수 있어보이지만 이진 탐색으로 풀지 않으면 시간 초과로 통과를 하지 못하기 때문이지 않을까 추측해본다.

접근 방법

심사관은 쉴 틈 없이 사람들을 심사한다고 가정하면, 심사관이 한 명을 심사하는데 걸리는 시간의 배수마다 사람을 심사할 수 있다. 따라서 시간이 k분 일 때, m분씩 걸리는 심사관이 심사할 수 있는 사람은 k/m의 몫이다. 따라서 특정 범위의 k분을 이분 탐색하면서 전체 심사관이 심사한 사람 수가 주어진 n명이 되는지 확인하면 된다.

이분 탐색은 첫 점과 끝 점의 범위를 전체 범위의 반씩 줄여나가면서 중간 점이 찾는 점과 일치해 나가는지 탐색해 간다.
예를 들어 1부터 20까지의 수 중 12를 찾는다고 했을 때,
다음과 같은 순서대로 탐색한다.

첫 점	끝 점	중간 점	결과
1	20	10	10 < 12
10 + 1	20	15	12 < 15
11	15-1	12	12 == 12

순차 탐색으로 하는 것과 달리 한 번 탐색할 때마다 범위를 반 씩 줄여 나가니, 시간 복잡도가 O(logN)이 된다.

답

function solution(n, times) {
    let [start, end] = [1, Number.MAX_SAFE_INTEGER]
    let result = Number.MAX_SAFE_INTEGER
    while (start <= end){
        let mid = Math.floor((start + end) / 2)
        const total = times.reduce((a, b) => a + Math.floor(mid/b), 0);
        if (total >= n) {
            end = mid - 1
            result = Math.min(result, mid)
        } else {
            start = mid + 1
        }
    }
    
    return result;
}

처음에 end를 time의 최댓값*N으로 설정했는데, 메모리 초과가 발생헀다.
그 이유를 생각해보니, time의 최댓값이 1,000,000,000이고, N 또한 1,000,000,000이면, end가 1,000,000,000,000,000,000(1경)이 되고, 이는 자바스크립트에서 저장할 수 있는 최대 정수인 9,007,199,254,740,991를 가뿐히 넘게 된다.

k분일 때, 심사한 사람을 구할 때, reduce를 썼다.

const total = times.reduce((a, b) => a + Math.floor(mid/b), 0);