문제

풀이 과정

요약

$distance$ 최대가 1,000,000,000 이다.
추정 값 $mid$ 를 활용한 이분 탐색으로 풀었다.

상세

1. 바위를 $n$ 개 만큼 제거 했을 경우, 출발, 도착을 포함한 각 노드간 사이의 거리의 최소값 가운데 가장 큰 값을 찾아야 한다.

2. 임의의 값 $mid$ 를 선정한 뒤, $mid$ 보다 작은 노드 사이의 거리가 존재하는 경우 해당 바위를 제거한다고 가정하자.

3. 주어진 $n$ 개 보다 바위가 많이 제거 된다면, $mid$ 를 줄이고, $n$ 개 보다 적게 혹은 동일하게 바위가 제거된다면 $mid$ 를 늘리면서 탐색하면 된다.

정답

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

  let [l, r] = [0, distance];
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    let [tn, pv] = [n, 0];
    for (let i = 0; i < rocks.length; i++)
      rocks[i] - pv < mid ? tn-- : (pv = rocks[i]);

    if (distance - rocks[rocks.length - 1] < mid) tn--;

    if (tn < 0) r = mid - 1;
    else {
      answer = mid;
      l = mid + 1;
    }
  }

  return answer;
}