[JS][프로그래머스]PCCP 기출문제 2번 / 퍼즐 게임 챌린지 : 이진 탐색, 대규모 배열의 최댓값 구하기 (Spread operator vs. reduce)

접근 방식

1. 처음에는 diffs의 최댓값을 maxLevel로 설정하고, 이를 1씩 줄여나가며 숙련도의 최솟값을 구하려 했다.
   1. 즉, 완전 탐색(Brute Force)을 이용해 문제를 해결하려 했다.
   2. diffs의 최댓값을 maxLevel로 설정하려고 한 이유는 이 값 이상으로 maxLevel을 설정하면 무조건 제한 시간(limit) 내에 모든 퍼즐을 해결할 수 있기 때문이다. (추가 시간 없이 해결되기 때문)
   3. 따라서 diffs의 최댓값 이상의 값을 maxLevel로 설정해야 하는데, 반환값은 숙련도의 최솟값이므로 diffs의 최댓값을 maxLevel로 설정한다.
2. 그러나 위의 방법은 최악의 경우 300억번의 연산이 필요하다.
   1. diffs[i] = 100,000, diffs.length = 300,000, limit = 1인 경우
   2. JS 코테 환경에서 1억번 이상의 연산은 시간 초과가 날 수 있다!
   3. 따라서 이럴 경우에는 이진 탐색, 누적합, 해시, 슬라이딩 윈도우, 투 포인터 등의 알고리즘을 고려해야 한다.
3. 범위가 큰 배열에서 특정 값을 구해야 하니 이진 탐색을 사용하자.
   1. maxLevel과 minLevel을 설정하고, 중간값인 midLevel을 통해 해당 값으로 limit 내에 통과할 수 있는지 판별해 나가며 리턴값(level)의 범위를 좁혀나가자.

❌ Solution 1 - tc 15~21 시간초과

소요 시간

• diffs[i]가 숙련도 이하일 때
  • `time_cur`
• diffs[i]가 숙련도보다 클 때
  • `(diff - level) × (time_cur + time_prev) + time_cur`
  • `time_cur`은 `time[i]`이고, `time_prev`는 `time[i-1]`이다.
    • → `i === 0`일 때 `time_prev`를 `0`으로 설정해주어야 참조 에러를 방지할 수 있다.

코드

// Binary search
// mid(숙련도)로 limit 내에 퍼즐을 풀 수 있다 → max = mid - 1
// mid로 limit 내에 퍼즐을 풀 수 없다 → min = mid + 1

// 소요 시간 = (diff - level) × (time_cur + time_prev) + time_cur
function solution(diffs, times, limit) {
    let minLevel = 1;
    let maxLevel = Math.max(...diffs);
    let level = minLevel;
    
    while (minLevel <= maxLevel) {
        const midLevel = Math.floor((minLevel + maxLevel) / 2);
        let totalTime = 0;    // 전체 소요 시간
        
        for (let i = 0; i < diffs.length; i++) {
            if (diffs[i] <= midLevel) {
                totalTime += times[i];
            } else {
                let timeCur = times[i];
                let timePrev = i === 0 ? 0 : times[i - 1];
                
                totalTime += (timeCur + timePrev) * (diffs[i] - midLevel) + timeCur;
            }
        }
        
        if (totalTime <= limit) {
            level = midLevel;
            maxLevel = midLevel - 1;
        } else {
            minLevel = midLevel + 1;
        }
    }
    
    return level;
}

문제 원인

배열 인덱스를 초과하지도 않았고, undefined나 null을 참조하지도 않아서 런타임에러 발생 원인을 파악하기 어려웠다.

 

'질문하기'에서 나랑 똑같은 테스트케이스에서 런타임 에러가 발생했다는 글이 있었고, 댓글에서는 최댓값 구하는 로직(`Math.max(...diffs)`)이 원인이라고 해서 스프레드 연산자에 대해 자세히 알아보았다.

 

스프레드 연산자를 사용할 경우에도 런타임 에러가 발생할 수 있다.

스프레드 연산자는 배열을 펼쳐서 인자로 전달하는 방식인데, 이 과정에서 배열의 모든 값을 스택에 복사하는 방식으로 동작한다. (= 배열을 통째로 스택에 올림)

따라서 배열의 길이가 수십만 이상이라면, JS 엔진의 call stack 깊이 제한에 걸려 실행이 불가할 수 있다.

✅ Solution 2

스프레드 연산자를 사용하지 않고 배열의 최댓값을 구하려면?

 

늘 누산기로만 사용하던 `reduce`를 사용하면 된다!

`reduce`는 내부적으로 반복문을 사용해 배열을 순회하므로, 스택에 값을 펼쳐놓지 않아 대규모 배열에서도 call stack의 한계를 초과하지 않고 안정적으로 동작한다.

reduce로 배열의 최대값 구하기

diffs.reduce((acc, cur) => Math.max(acc, cur), 0);	// diffs[i] >= 1이라 0을 초기값으로 설정함

diffs.reduce((max, num) => (max > num ? max : num));

코드

function solution(diffs, times, limit) {
    let minLevel = 1;
    let maxLevel = diffs.reduce((acc, cur) => Math.max(acc, cur), 0);	// 달라진 부분
    let level = minLevel;
    
    while (minLevel <= maxLevel) {
        const midLevel = Math.floor((minLevel + maxLevel) / 2);
        let totalTime = 0;
        
        for (let i = 0; i < diffs.length; i++) {
            if (diffs[i] <= midLevel) {
                totalTime += times[i];
            } else {
                let timeCur = times[i];
                let timePrev = i === 0 ? 0 : times[i - 1];
                
                totalTime += (timeCur + timePrev) * (diffs[i] - midLevel) + timeCur;
            }
        }
        
        if (totalTime <= limit) {
            level = midLevel;
            maxLevel = midLevel - 1;
        } else {
            minLevel = midLevel + 1;
        }
    }
    
    return level;
}

---

TIL

• JS 코테 환경에서 1억번 이상의 연산은 위험하다. 접근 방식을 설계할 때 시간 복잡도를 먼저 계산하고, 그에 맞는 적절한 알고리즘을 선택하자.
• 스프레드 연산자가 런타임 에러의 원인이 될 수 있다.
  • 특히 배열의 길이가 수십만 이상일 경우 call stack의 한계로 인해 에러가 발생할 수 있다.
• reduce를 활용해 배열의 최댓값을 구할 수 있다.
  • 누산기 역할 외에도 최댓값/최솟값, 각 원소의 개수 세기, 그룹화 등 다양한 용도로 활용 가능하다. https://www.daleseo.com/js-array-reduce/

 

---

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

프로그래머스