[JS] 징검다리 건너기

문제

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

프로그래머스

 

풀이

이 문제는 이분탐색으로 풀이해야한다.

 

건너야 하는 돌들을 탐색해야 하나 생각했지만, 사실 건널 수 있는 인원수를 이분탐색 해야한다. 인원수는 최소 1명, 최대 2억명이다. 이유는 바위의 내구성을 나타내는 숫자의 범위는 1 ~ 2억이기 때문이다. 

 

최소값이 최대값 보다 적을 때까지 탐색을 진행한다.

 

이분탐색을 진행하며 중간값을 각 바위의 숫자에 빼준다. 뺀 결과값이 0이하이면 중간값의 인원수만큼 건너갈 수 없다는 것을 의미한다. 이 때 최소값을 중간값 + 1로 설정해준다.

 

만약 다 건널 수 있음에도 건널 수 있는 인원의 최대값을 구해야하기 때문에 최대값을 중간값-1로 설정하며 탐색을 진행한다.

 

코드

function solution(stones, k) {
  let min = 1;
  let max = 200000000;
    
  while (min <= max) {
    const mid = (min + max) / 2 >> 0;
    let cnt = 0;
    let flag = false;
        
    for (const val of stones) {
      cnt = val - mid <= 0 ? cnt + 1 : 0;
      if (cnt === k) {
        flag = true;
        break;
      }
    }
    flag ? max = mid - 1 : min = mid + 1;
  }
    
  return min;
}