D+44 Lv4 징검다리 (이분탐색)

문제

출발지점부터 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 함수를 작성해주세요.

제한사항
도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
바위는 1개 이상 50,000개 이하가 있습니다.
n 은 1 이상 바위의 개수 이하입니다.
입출력 예
distance rocks n return
25 [2, 14, 11, 21, 17] 2 4
입출력 예 설명
문제에 나온 예와 같습니다.

풀이

2) 기억할 풀이

맨 처음에 최소거리와 최대거리를 그냥 지정하고 while문 안에서 이분탐색 그대로 진행하면 되는 것이었다.

function solution(distance, rocks, n) {
    rocks.sort((a, b) => a - b); // 바위 정렬
    let left = 1; // 최소 거리
    let right = distance; // 최대 거리
    let answer = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let count = 0; // 제거할 바위 개수

        let lastPosition = 0; // 마지막 위치
        for (let rock of rocks) {
            if (rock - lastPosition < mid) {
                count++; // 바위를 제거해야 함
            } else {
                lastPosition = rock; // 현재 바위 위치로 업데이트
            }
        }

        // 마지막 바위와 도착지점 사이의 거리 체크
        if (distance - lastPosition < mid) {
            count++;
        }

        if (count <= n) {
            answer = mid; // 최소 거리 가능
            left = mid + 1; // 더 큰 거리 탐색
        } else {
            right = mid - 1; // 더 작은 거리 탐색
        }
    }

    return answer;
}

1) 처음 접근했던 방식

rocks 배열에서 무작위로 n개를 버리고, 남은 rocks배열에서 다음 코드와 함께 이분 탐색을 실행하고, arr배열에 거리의 최솟값을 push 한 다음
Math.max(...arr) 로 정답을 리턴해주면 되지 않을까?

let left = rocks.sort((a,b)=> a-b)[0]
let right = distance - left