[프로그래머스 Lv4] 사칙연산 - Javascript 풀이

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

프로그래머스

---

문제

정수와 +, - 연산자가 번갈아 들어 있는 배열이 주어졌을 때,
괄호를 적절히 배치하여 만들 수 있는 계산 결과 중 최댓값을 구하는 문제

 

생각

단순히 왼쪽부터 순차 계산하면 괄호의 효과를 전혀 반영할 수 없다.
특히 − 연산은 결합법칙이 성립하지 않기 때문에
중간에 어떤 값을 먼저 계산하느냐에 따라 결과가 크게 달라진다.

그래서 구간별로 만들 수 있는 최댓값과 최솟값을 모두 관리하는 DP가 필요하다고 생각했다.

 

문제풀이

테이블을 정의해보자.

Max[i][j] : i번째 숫자부터 j번째 숫자까지 계산해서 얻을 수 있는 최댓값
Min[i][j] : i번째 숫자부터 j번째 숫자까지 계산해서 얻을 수 있는 최솟값

 

여기서 i, j는 숫자의 인덱스이다.
연산자는 숫자 사이에 하나씩 존재하므로,
연산자 op[k]는 num[k] 와 num[k+1] 사이에 위치한다.

 

구간의 길이가 1이라면,
단순히 해당 숫자 하나이므로

Max[i][i] = Min[i][i] = num[i]

 

 

현재 구간이 i부터 j라면,
모든 k (i ≤ k < j)에 대해 연산자 op[k]를 기준으로 왼쪽/오른쪽 구간을 나눌 수 있다.

 

이때 op[k]가 +인지 -인지에 따라 계산값이 달라지므로
왼쪽/오른쪽 구간의 최댓값/최솟값 조합을 모두 고려해야 한다.

 

점화식은 다음과 같다.

왼쪽: i ~ k
오른쪽: k+1 ~ j

가능한 조합은 총 네 가지:

Max[i][k] op Max[k+1][j]
Max[i][k] op Min[k+1][j]
Min[i][k] op Max[k+1][j]
Min[i][k] op Min[k+1][j]

 

이 모든 값 중 최댓값 → Max[i][j]
모든 값 중 최솟값 → Min[i][j]

이렇게 결정한다.

 

시간복잡도는 구간 DP의 전형적인 구조라
O(N³)이다.

 

코드

function solution(arr) {
    const nums = [];
    const ops = [];

    // 숫자와 연산자 분리
    for (let i = 0; i < arr.length; i++) {
        if (i % 2 === 0) nums.push(Number(arr[i]));
        else ops.push(arr[i]);
    }

    const n = nums.length;

    // DP 테이블 초기화
    const Max = Array.from({ length: n }, () => Array(n).fill(-Infinity));
    const Min = Array.from({ length: n }, () => Array(n).fill(Infinity));

    // 길이 1 구간 초기화
    for (let i = 0; i < n; i++) {
        Max[i][i] = nums[i];
        Min[i][i] = nums[i];
    }

    // a op b 계산 함수
    function calc(a, b, op) {
        return op === '+' ? a + b : a - b;
    }

    // 구간 길이 len = 2 ~ n
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {

            const j = i + len - 1;

            for (let k = i; k < j; k++) {
                const op = ops[k];

                const candidates = [
                    calc(Max[i][k], Max[k+1][j], op),
                    calc(Max[i][k], Min[k+1][j], op),
                    calc(Min[i][k], Max[k+1][j], op),
                    calc(Min[i][k], Min[k+1][j], op),
                ];

                Max[i][j] = Math.max(Max[i][j], ...candidates);
                Min[i][j] = Math.min(Min[i][j], ...candidates);
            }
        }
    }

    return Max[0][n-1];
}