[프로그래머스] 징검다리

문제

징검다리

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

 

 

풀이

설명

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값을 구하는 문제입니다.

 

이분탐색을 통해 해결할 수 있습니다.

 

1. 바위들을 오름차순으로 정렬해주고, 편의상 도착점을 배열에 추가해줍니다.
2. 거리의 최솟값은 1, 최댓값은 도착점으로 초기화합니다.
3. 중간값에 대해서 조건을 만족하는지 확인합니다.
   1. 제거한 바위 개수가 n개 이하라면, 해당 값을 저장하고 최솟값을 높입니다.
   2. n개를 초과한다면 최댓값을 낮춥니다.

 

예시 코드

function solution(distance, rocks, n) {
  let left = 1;
  let right = distance;
  let answer = 0;

  rocks.sort((a, b) => a - b);
  rocks.push(distance);

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (canRemove(mid, n)) {
      answer = mid;
      left = mid + 1;
    } else right = mid - 1;
  }

  return answer;

  function canRemove(dist, n) {
    let cnt = 0;
    let lastRock = 0;

    for (const rock of rocks) {
      if (rock - lastRock < dist) cnt++;
      else lastRock = rock;
    }

    return cnt <= n;
  }
}