출처

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

처음 풀이

설명

• stones를 sort해서, 최대값의 index를 0으로 잡고,
  징검다리 건너기를 실패하면, idx++ 했습니다.
• 가장 먼저 통과하는 최대값 === answer
• 정확성은 통과했지만, 효율성을 통과하지 못합니다.

function solution(stones, k) {
    const arr = [...stones].sort((a,b)=>b-a)
    const set = new Set(arr)
    let idx = 0
    
    while (idx < set.size) {
        let maxV = [...set][idx]
        let flag = true
        let cnt = 0
        
        for (let i=0; i<stones.length; i++) {
          	// stone이 maxV보다 같거나 크다 : 건널 수 있다.
          	// stone이 maxV보다 작다 : 건널 수 없다.
            const stone = stones[i]
            if (stone >= maxV) cnt = 0
            else cnt ++
          	// [종료조건]. 건널 수 없는 횟수(cnt)가 k와 같거나 커지면, 징검다리 건너기실패.
            if (cnt >= k) {
                idx ++
                flag = false
                break
            }
        }
        // [종료조건]. 최대값부터 순서대로 내려오니까, 가장 먼저 통과한 값이 answer.
        if (flag) return maxV
    }
    
}

개선한 풀이(이진 탐색)

설명

• 배열 요소의 범위가 매우 넓으므로(1 이상 200,000,000 이하인 자연수), 최대값부터 모든 인덱스를 탐색하지 않고, 이진 탐색을 활용합니다.
• 기존 풀이의 maxV를 계산하는 로직을 그대로 이진탐색으로 대체했고, 풀이가 통과되었습니다.

function solution(stones, k) {
    var answer = 0;
  	// 배열 크기가 매우 커지면, 스프레드 연산자에서 에러 발생함.
    // let right = Math.max(...stones)
    // let left = Math.min(...stones)
    let right = stones[0];
    let left = stones[0];

    for (let i = 1; i < stones.length; i++) {
        right = Math.max(right, stones[i]);
        left = Math.min(left, stones[i]);
    }

    while (left <= right) {
        let mid = Math.floor((left+right)/2)
        let cnt = 0
        let flag = true
        
        for (let i=0; i<stones.length; i++) {
            const stone = stones[i]
            if (stone >= mid) cnt = 0
            else cnt ++

            if (cnt >= k) {
                flag = false
                break
            }
        }
        
      	// 징검다리 건너기 성공했으면, 숫자(mid)를 높여봄.
        if (flag) {
            left = mid + 1
            answer = mid
        // 건너기 실패했으면, 숫자(mid)를 낮춤.
        } else {
            right = mid - 1
        }
    }
    // 이진탐색이 끝나면, 징검다리 건너기에 성공한 최대값이 answer에 할당되어 있음.
    return answer

}

배운것

• 파이썬의 max(arr)은 JS에서 Math.max(...arr)와 같다.
• 하지만, JS의 스프레드 연산자는 매우 긴 길이의 입력배열이 들어가면, "Maximum call stack size exceeded" error를 반환한다. 따라서, 제한사항이 특별히 길면, 반복문을 통해 계산하는 것이 안전하다.
• 이진 탐색이 중간에 종료되지 않고 끝까지 마치면, left에는 right+1이 할당되어 있고, right에는 가능한 최대값이 할당되어있다.
• 따라서, 이 로직같은 경우에는 매번 answer에 mid를 할당하지 않고, 마지막에 return right를 해도 통과된다.
• 제한사항의 범위가 특별히 길면, 일단 이진탐색 써놓고 보자.