프로그래머스 | Level3. 징검다리 건너기 (이분탐색)

✅ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

 

📌 접근 방법

• 이분탐색

stones 배열에 있는 원소들의 값은 1이상 200,000,000 이하의 자연수다.

따라서 니니즈 친구들이 최대 200,000,000명이 건널 수 있다.

정답은 1~200,000,000 사이에 존재 하므로, 이분탐색으로 1~200,000,000 사이를 탐색하며 정답이 되는지 확인한다.

 

아래 코드에서 cntNum 함수는 현재 mid값이 정답이 될 수 있는지 확인하는 함수다.

동작을 설명하자면, stones에 저장되어있는 값에서 mid값을 뺀 값을 구한다.

그 값이 0 또는 음수 이면, 해당 돌은 밟을 수 없는 돌이 된다.

그 돌이 연속되는 구간의 길이는 점프해서 지나가야하는 돌다리 구간이다.

따라서 해당 mid값에서 점프해서 지나가야하는 돌다리 구간중 가장 긴 구간을 구하여 반환한다.

가장 짧은 구간을 반환하면 안되는 이유는, 음수 또는 0이 한 구간이라도 존재한다면 반환값은 항상 1이 되기 때문이다.

 

✔️ 해결 코드

  function cntNum(mid, stones, k) {
    // mid를 뺀 stones에서 음수 또는 0으로 이루어진
    // 연속된 k 길이 이상의 구간이 존재하는지 확인 => 있다면 구간 길이의 최대값을 담는다
    // 반환값은 구간의 길이.
    let result = 0,
      n = stones.length;

    let tp = 0,
      flag = false;
    for (let i = 0; i < n; i++) {
      if (stones[i] - mid <= 0) {
        tp++;
        flag = true;
      } else if (flag) {
        result = Math.max(result, tp);
        tp = 0;
        flag = false;
      }
    }
    if (flag) {
      result = Math.max(result, tp);
    }
    return result;
  }
  function solution(stones, k) {
    let answer = 200000000;
    let lt = 0,
      rt = 200000000;

    while (lt <= rt) {
      let mid = Math.floor((lt + rt) / 2);

      if (cntNum(mid, stones) >= k) {
        answer = mid;
        rt = mid - 1;
      } else {
        lt = mid + 1;
      }
    }
    return answer;
  }

 

 

✔️ 디버깅 코드

  console.log(solution([23, 41, 86, 6, 38, 90, 66, 11, 34, 1, 6, 2], 5)); // 34
  console.log(solution([1, 3, 1], 2)); // 3
  console.log(solution([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3)); //3
  console.log(solution([1, 1, 4, 2, 2, 1, 4, 2, 5, 1], 3)); //2
  console.log(solution([1, 1, 4, 2, 1, 4, 1, 2, 5, 1], 3)); // 4
  console.log(solution([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 3)); // 1
  console.log(solution([3, 3, 3, 3, 3, 3, 3, 3, 3, 3], 3)); // 3
  console.log(solution([2, 4, 5, 3, 2, 1, 4, 2, 1, 1], 3)); // 2

 

 

 

 

---

 

📌 잘못된 접근

슬라이딩 윈도우로 해결하려 했다. 그렇게 하였더니 효율성 13번을 통과하지 못했다.

13번 효율성은 돌다리 구간이 오름차순이기 때문에, 계속해서 구간 내의 최대값을 찾게 되어 시간복잡도가 O(n^2)이된다. 

 

✔️ 잘못된 코드

 function solution(stones, k) {
    let answer = 900000000;
    let n = stones.length;
    // k구간내 가장 작은 값
    let max = 0;
    let max_idx = 0;

    for (let i = 0; i < k; i++) {
      if (max < stones[i]) {
        max = stones[i];
        max_idx = i;
      }
    }

    let lt = 0,
      rt = k;
    for (; rt < n; rt++) {
      // 최소값 갱신
      if (max_idx < lt) {
        max = 0;
        for (let i = lt; i < rt; i++) {
          if (max < stones[i]) {
            max = stones[i];
            max_idx = i;
          }
        }
      }
      answer = Math.min(answer, max);

      lt++;
    }
    if (max_idx < lt) {
      max = 0;
      for (let i = lt; i <= rt; i++) {
        if (max < stones[i]) {
          max = stones[i];
          max_idx = i;
        }
      }
    }
    answer = Math.min(answer, max);
    return answer;
  }