[programmers/js] 징검다리

징검다리

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

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치	각 바위 사이의 거리	거리의 최솟값
[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

풀이

이분 탐색을 통해 해결합니다.
이분 탐색을 통해 mid(바위 사이 거리) 보다 적은 거리에 있는 바위를 제거합니다.
제거한 바위 수가 n보다 작으면 크기를 줄여갑니다.

function solution(distance, rocks, n) {
    rocks.sort((a, b) => a - b);   // 바위 위치 정렬
    rocks.push(distance);          // 도착 지점도 마지막 바위로 추가

    let left = 1;
    let right = distance;
    let answer = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2); // 최소 거리 후보
        let removed = 0;    // 제거한 바위 수
        let prev = 0;       // 이전 바위 위치

        for (let i = 0; i < rocks.length; i++) {
            const gap = rocks[i] - prev;
            if (gap < mid) {
                removed++;  // 거리가 너무 좁으면 바위 제거
            } else {
                prev = rocks[i]; // 바위 유지
            }
        }

        if (removed > n) {
            right = mid - 1; // 너무 많이 제거 → 최소 거리 줄임
        } else {
            answer = mid;    // 현재 거리 저장
            left = mid + 1;  // 더 큰 거리로 도전
        }
    }

    return answer;
}