프로그래머스 LEVEL 3(징검다리 건너기)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2022-12-24

  • 해결 방법 :

    • 이분탐색을 통해 문제 해결
      • 이분탐색의 범위는 1 ~ 200000000
      • 이분탐색을 수행하며 mid 보다 작은 디딤돌 값이 k개 이상이면(건널 수 없는 경우) mid의 왼쪽 탐색
      • 그 외의 경우(건널 수 있는 경우) mid의 오른쪽 탐색

  • 회고 :

    • x

  • 코드

    function solution(stones, k) {
  let left = 1,
    right = 200000000;

  const isLeft = (mid) => {
    let count = 0;

    for (let i = 0; i < stones.length; i++) {
      count = stones[i] <= mid ? count + 1 : 0;

      if (count === k) return true;
    }

    return false;
  };

  while (left <= right) {
    const mid = Math.ceil((left + right) / 2);

    if (isLeft(mid)) right = mid - 1;
    else left = mid + 1;
  }

  return left;
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges