Programmers 징검다리

shleecloud·2022년 3월 30일

JavaScript algorithm

Algorithm

목록 보기

15/16

들어가며

이 문제 패턴은 한 번 봤다. 백준의 공유기 설치 문제와 굉장히 닮았다. 예전에 할 때도 못풀었던 것 같은데 여전히 힘들었다. 답을 봤는데도 어려운 문제. 이분탐색의 핵심은 한 문장으로 정리된다.

해설

이분탐색의 핵심은 먼저 답을 정해놓고 그 답이 맞는지 찾아나간다.

처음 답은 시작과 끝의 중간 지점으로 잡는다.
값이 맞는지 확인한다.
예상 답보다 높으면 위를 줄이고 낮으면 아래를 높인다.
돌은 시작지점부터 첫 돌까지 위치를 확인한다. 그래서 for문의 시작이 1부터다.
count > n 이 만족해야되니 right 값을 반환한다.

문제

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

function solution(distance, rocks, n) {
  rocks = [0, ...rocks.sort((a, b) => a - b), distance];
  let left = 0,
    right = distance;

  while (left <= right) {
    let mid = Math.floor((right + left) / 2),
      count = 0,
      now = 0;

    // * 이분탐색 실행
    // ! 1부터 시작해야 0번 돌과 1번 돌의 거리를 계산할 수 있음
    for (let i = 1; i < rocks.length; i++) {
      if (rocks[i] - now < mid) {
        count++;
      } else {
        now = rocks[i];
      }
    }
    // * 이분탐색 판별
    if (count > n) right = mid - 1;
    else left = mid + 1;
  }

  return right;
}

console.log(solution(25, [2, 14, 11, 21, 17], 2));