BinarySearch

[dlehdanakf]

개요

• 이분탐색은 두 개의 포인터를 두고 구간을 이분하는 중간지점을 구한 뒤, 해당 중간지점이 정답에 부합하는 여부에 따라 탐색범위를 다르게 좁혀나가는 알고리즘이다.
• 여기서 중요한점은 구간이 정렬되어있어야한다는 것!
• 구간이 되는 재료들은 문제에 따라 연속된 수일 수도 단순 배열일 수도 있기 때문이다.
• 따라서 정렬을 선행함으로서 중간지점을 구할 수 있다.
• A, B 두 포인터가 있고 중간지점 M 이 있을 때, M이 정답에 합당할 경우 M, B 로 두고 다시 재귀호출을 하는 방식이다.

예시

입국심사

• 문제 바로가기
• 여러명의 입국심사관이 있고 대기인원이 N명 있을 때 최소한의 걸리는 시간은?

해결과정

• 처음에는 이분탐색 알고리즘을 떠올리지 못했다. (물론 문제의 카테고리는 이분탐색이지만) 어떤 구간에 대해 이분탐색을 수행할 것인지 파악하는 능력이 중요한 것 같다. 이분탐색에 대해 알고 있더라도 구간을 제대로 선정하지 못한다면 문제를 해결하지 못할 것이다.
• 보통 구간은 최선의 경우 부터 최악의 경우까지로 한다.
• 이 문제에서는 1분만에 (그럴 가능성은 전혀 없지만) 모든 입국심사를 끝내는 것이 최선의 경우고, 가장 입국심사가 오래걸리는 심사관이 모든 대기인원을 심사하는 시간이 최악이 될 것이다.
• 일단 입국심사관을 정렬한다.
• left 포인터를 1, right 포인터를 N * M 으로 초기화한다.
• 탐색을 끝내는 조건(루프문을 탈출하는 조건)은 left 포인터가 right 포인터보다 같거나 커지는 시점이다.
• 처음 이분탐색을 구현할 때 당황스러웠던 고민인데, 가운데값을 구하지만 해당 값이 소수면 어떡할 것인가? 그냥 버림 한다.
• 중간값을 구한 뒤, 해당 중간값일 때 입국심사를 몇명 할 수 있는지 나눗셈을 통해 구해본다.
• 중간값이 정답에 부합하는 여부에 따라 left, right 포인터의 값을 바꿔준다.

function solution(n, times) {
    times.sort((a, b) => b - a);
    const { length } = times;
    let left = 1, right = times[0] * n;
    let answer = right;

    while(left <= right) {
        let middle = Math.floor((left + right) / 2), count = 0;
        for(let i = 0; i < length; i++) {
            count += Math.floor(middle / times[i]);
        }

        if(count >= n) {
            answer = Math.min(answer, middle);
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }

    return answer;
}