[Lv.3] 징검다리 건너기 - JavaScript

문제

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

프로그래머스

 

풀이

친구들 수를 하나씩 늘려나가는 방법으로 풀다가 시간 초과가 나서 다른 코드를 참고했다.

이분탐색으로 풀어야하는 문제! 

숫자 범위가 크게 주어지는 경우 높은 확률로 이분탐색 문제라고 한다..

 

코드

function solution(stones, k) {
  let min = 1;
  let max = 200000000;

  while (min <= max) {
    const mid = ((min + max) / 2) >> 0; // 2로 나누고 소숫점이하 버림
    const copy = stones.slice();

    let zeroCnt = 0; // 0이 3번 반복되면 탈출할거야

    for (let i = 0; i < copy.length; i++) {
      copy[i] -= mid; // 돌의 수 - 현재 검사할 친구들의 수
      zeroCnt = copy[i] <= 0 ? zeroCnt + 1 : 0; // 연속되는 0의 개수를 세어 줌
      // 연속되는 0의 개수가 k개가 되는 순간
      if (zeroCnt === k) {
        break;
      }
    }

    // 연속되는 0의 개수가 k개이면 min값을 조작하고 아니면 max을 조작한다.
    if(zeroCnt===k) {
      max = mid - 1
    } else {
      min = mid + 1
    }
  }
  return min; // 최솟값은 min에 저장
}

=> 여전히 효율성 테스트 딱 1개를 뚫지 못하는 코드,,, 주말동안 다시,,해보기