[JS] 프로그래머스 짐검다리

문제 링크

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

알고리즘

1. 최소 거리를 이분 탐색한다.

2. rocks를 순회하면서 거리가 더 짧으면 제거한다 (skip)

3. 제거한 개수가 n이하이면 정답 후보가 된다.

왜 n일 때가 아니라 n이하인가?

• n이하일 땐 아무 곳을 제거해서 n을 맞출 수 있기 때문이다.

코드

function solution(distance, rocks, n) {
    rocks.sort((a, b) => a - b).push(distance);

    var ans = 0, l = 1, r = distance;
    while (l <= r) {
        var m = Math.floor((l + r) / 2);
        var prev = 0, remove = 0;
        rocks.filter(rock => {
            if (rock - prev < m)
                remove++;
            else
                prev = rock;
        })

        if (remove <= n){
            ans = Math.max(ans, m);
            l = m + 1;
        }
        else 
            r = m - 1;
    }
    return ans;
}