[JS] 징검다리 건너기

프로그래머스 징검다리 건너기

• 난이도 LV.2

문제 풀이

프로그래머스 입국 심사와 함께 풀면 좋을 것 같다 :)
'인원'을 이분 탐색하여 풀었다.

 

1. 인원을 이분 탐색한다.

- left : 0

- right : 200000000  ( Math.max(...stones) 를 할 수도 있지만 ! 런타임 에러가 난다 😅)

 

2. 해당 mid 값이 가능한지 검사한다.

검사하는 방법은 간단하다. 해당 mid의 값보다 적은 stone 값을 계산하여,

그 stone들이 연속적으로 k번 반복되는지 확인한다.

k번 반복되면, 그 인원으로 건너기 불가능한 것이고

k번이 반복되는 경우가 없으면, 그 인원으로 건너기가 가능한 것이다.

const available = (people, stones, max) => {
  let count = 0;

  for (let stone of stones) {
    if (stone < people) {
      count++;
      if (count >= max) return false;
    } else count = 0;
  }

  return true;
};

 

위에 로직만 찾는다면 쉽게 풀 수 있는 문제였다.. 😅 하지만 이걸 찾는게 어려웠다.

 

코드

const available = (people, stones, max) => {
  let count = 0;

  for (let stone of stones) {
    if (stone < people) {
      count++;
      if (count >= max) return false;
    } else count = 0;
  }

  return true;
};

function solution(stones, k) {
  var answer = 0;
  let left = 0;
  let right = 200000000;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const result = available(mid, stones, k);

    if (result) {
      left = mid + 1;
      answer = mid;
    } else {
      right = mid;
    }
  }

  return answer;
}