프로그래머스[Level 4] 징검다리(이진탐색, 결정 알고리즘)

문제

제한 사항

입출력 예

풀이

const count = (rocks, mid) => {
  let cnt = 0;
  let prev = 0; // 이전 돌의 위치, 첫위치는 항상 0
  for (let i = 0; i < rocks.length; i++) {
    if (rocks[i] - prev <= mid) {
      // 현재 돌의 위치와 전 돌의 위치의 차이가 mid보다 작으면 이 돌은 제거 가능하다.
      cnt++;
    } else {
      prev = rocks[i];
    }
  }
  return cnt;
};
const solution = (distance, rocks, n) => {
  let answer = 0;
  let lt = 1,
    rt = distance;

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

  while (lt <= rt) {
    const mid = Math.floor((lt + rt) / 2); // 거리의 최소값
    // 바위 사이의 거리가 mid보다 작거나 같으면 제거 할 수 있는 바위이다.
    let removeCount = 0;

    removeCount = count(rocks, mid); //거리의 최소값이 mid일 때 제거 가능한 바위의 수

    if (removeCount > n) {
      rt = mid - 1; // 범위를 줄여야함
    } else {
      lt = mid + 1;
      answer = Math.max(answer, lt);
    }
  }
  return answer;
};

• mid값을 돌 사이 거리의 최솟값으로 놓고, 하나의 돌과 그 바로 앞 돌을 비교하여 거리가 mid 이하이면 현재의 돌을 제거 할 수 있다. 이를 이용한 count 함수를 만들었다.
• rocks 배열은 단순히 돌의 위치를 무작위하게 넣은 배열이기 때문에 정렬해도 괜찮다. 정렬하면 안되는 경우의 문제도 있다.
• count를 할 방법과 mid를 어떤 기준으로 둘 것인지 정하면 결정 알고리즘의 패턴으로 코드를 작성하면 된다.
• 원래의 결정 알고리즘은 최적의 경우(최솟값)을 찾을 때까지 반복하여 답을 찾지만 이 문제의 경우 거리의 최소값 중 최대값을 구하는 것이기 때문에 answer = Math.max(answer, lt) 로 답을 구해주었다.