프로그래머스 퍼즐게임 챌린지 - 이진탐색, 스프레드 연산자 RangeError

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

퍼즐을 해결할 수 있는 가장 최소한의 난이도를 찾는 문제
문제 해결 방법은 단순하지만 이진탐색을 사용하지 않으면 시간초과가 발생하는 전형적인 이진탐색 문제이다.

첫번째 풀이 ❌ (시간초과)

function badSolution(diffs, times, limit) {
    let answer = 1;
    let curr = 0;
    
    for(let i=0; i<diffs.length; i++){
        if(diffs[i] > answer){
            curr += (times[i-1] + (times[i] || 0)) * (diffs[i] - answer) + times[i];
        } else {
            curr += times[i];
        }
        
        if(limit < curr) {
            i=-1;
            answer++;
            curr = 0;
            continue;
        }
    }
    
    return answer
}

단순하게 해결될 때까지 레벨을 1씩 증가시키면서 풀이를 진행한다.
테스트 15, 16, 17, 18, 21 에서 실패(시간 초과)가 발생한다.

두번째 풀이 ❌ (런타임에러)

function solution(diffs, times, limit) {
    let min = 1;
    let max = Math.max(...diffs);
    let answer = max;
  
    while (min <= max) {
        let mid = Math.floor((min + max) / 2);
        if (canSolve(mid)) {
            answer = mid;
            max = mid - 1;
        } else {
            min = mid + 1;
        }
    }

    function canSolve(level){
        let curr = 0;
        for(let i=0; i<diffs.length; i++){
            if(diffs[i] > level) {
                curr += (times[i-1] + (times[i] || 0)) * (diffs[i] - level) + times[i];
            } else curr += times[i];
            if(limit < curr) return false
        }
        return true
    }
    
    return answer
}

위의 풀이를 canSolve라는 함수선언문으로 변경하여고, 가장 어려운 난이도를 max로 설정하면서 이진탐색으로 풀어내었다.
하지만 문제 15번부터 런타임에러가 발생한다.

스프레드 연산자로 인해 발생하는 런타임에러

함수 인자 값으로 스프레드 연산자를 사용하면 그 인자들을 스택에 올려서 함수에 전달하게 된다. 때문에 Math.max(...hugeArray)와 같이 함수인자로 길이가 매우 긴 배열을 넘기게 되면 RangeError: Maximum call stack size exceeded 가 발생하게 된다.

위 풀이에서는 Math.max(...diffs)을 통해 이진탐색의 max 값을 설정하려 하였는데, 문제의 제한사항에서 diffs와 times 배열의 길이를 0 < n ≤ 300,000 이었기 때문에, 프로그래머스 상에서 런타임 에러가 발생하게 된 것이다.

세번째 풀이 ⭕️

function solution(diffs, times, limit) {
    let min = 1;
    let max = 0;
    diffs.forEach((v) => max = Math.max(v, max))
        
    let answer = max;
    while (min <= max) {
        let mid = Math.floor((min + max) / 2);
        if (canSolve(mid)) {
            answer = mid;
            max = mid - 1;
        } else {
            min = mid + 1;
        }
    }

    function canSolve(level){
        let curr = 0;
        for(let i=0; i<diffs.length; i++){
            if(diffs[i] > level) {
                curr += (times[i-1] + (times[i] || 0)) * (diffs[i] - level) + times[i];
            } else curr += times[i];
            if(limit < curr) return false
        }
        return true
    }
    
    return answer
}

diffs.forEach((v) => max = Math.max(v, max))를 통해 max값을 지정하였다.
다른 사람들의 풀이를 보니, diffs.reduce((acc, cur) => Math.max(acc, cur), 1)와 같이 바로 최대값을 선언할 수도 있었다.
또한, sumT = 2n; 과 같이 BigInt 타입을 사용해서 이진탐색과 같이 매우 큰 값을 다루는 문제에서 더욱 안전하게 풀이를 진행할 수 있었다.