[프로그래머스] 1843 사칙연산 - JAVA
문제
https://school.programmers.co.kr/learn/courses/30/lessons/1843
문제 분석
조건
숫자와 연산자(+,-)로 이루어진 배열이 주어진다. 이 식에 괄호를 추가하여 바뀐 연산 순서에 따라 만들 수 있는 최댓값을 구하는 문제이다.
풀이방법
괄호의 위치에 따라 결과가 달라지므로 모든 경우의 수를 고려해야한다. 왜냐하면 -연산자일 경우 뒷 숫자가 작을수록 결과값을 더 크게 만드는 경우가 있다. 그래서 값을 다루려면 연산 과정에서 최댓값과 최솟값을 동시에 고려해야한다.
코드와 예제를 기반으로 설명을 하자면, `maxDp[start][end]` 는 `start`번째 숫자부터 `end`번째 숫자까지 연산 결과 중 최댓값을 의미하고,
`minDp[start][end]`는 `start`번째 숫자부터 `end`번째 숫자까지 연산 결과 중 최솟값을 의미한다.
그리고 연산자가 무엇인지가 중요한데,
연산자가 +인 경우, max = 최댓갑 + 최댓갑이고, min = 최솟값 + 최솟값을 해야하지만,
-인 경우엔, max = 최댓값 - 최솟값, min = 최솟값 - 최댓값을 해줘야한다.
첫번째 예제를 그림으로 나타내면 아래와 같다. 편의상 max와 min 값을 한 테이블에 그리고, `dp[i][i]`를 각각 `i`번째 숫자로 초기화를 해 주었다.
가장 먼저 start 인덱스를 기준으로 오른쪽으로 1번째 숫자(=`length`)까지 괄호를 쳤다고 계산을 해보면 구해야 할 값은 `dp[start][end]`이고, end = start + length가 된다. 각각의 숫자를 기준으로 1번째 숫자까지 연산을 한 값은 연산자와 상관없이 두 수를 단순 연산한 값이므로 아래 그림처럼 바뀐다.
이제 `length`이 2일 경우, `dp[0][2]`부터 살펴보면 식으로 나타냈을때 연산순서는 `1 - (3 + 5)`, `(1 - 3) + 5` 이렇게 2가지가 된다. 이를 식으로 나타내면 `dp[0][2] = dp[0][0] - dp[1][2]`, `dp[0][2] = dp[0][1] + dp[2][2]`인 것이다. 이때 dp를 나누는 부분에서 분기점`split`이 생기게 된다.
- `split`=0:`dp[0][0] - dp[1][2]`의 경우 -연산자
- maxDp[0][2] = maxDp[0][0] - minDp[1][2] = 1 - 8 = -7
- minDp[0][2] = minDp[0][0] - maxDp[1][2] = 1 - 8 = -7
- `split`=1:`dp[0][1] + dp[2][2]`의 경우 -연산자
- maxDp[0][2] = maxDp[0][1] + maxDp[2][2] = -2 + 5 = 3
- minDp[0][2] = minDp[0][1] + minDp[2][2] = -2 + 5 = 3
- 즉 maxDp[0][2] = `Math.max(maxDp[0][0] - minDp[1][2], maxDp[0][1] + maxDp[2][2])` = max(-7, 3) = 3
- minDp[0][2] = `Math.min(minDp[0][0] - maxDp[1][2], minDp[0][1] + minDp[2][2])` = min(-7, 3) = -7
마지막으로 전체 구간인 `length = 3`, 즉 `dp[0][3]`을 계산할 차례다. 이 값을 구하면 전체 식의 최댓값을 알 수 있다. 1-3+5-8을 계산하는 경우는 아래와 같이 세 가지로 나눌 수 있다.
- `split`=0: dp[0][0] - dp[1][3] (1과 3 사이 - 연산)
- 최댓값: maxDp[0][0] - minDp[1][3] = 1 - 0 = 1
- 최솟값: minDp[0][0] - maxDp[1][3] = 1 - 6 = -5
- `split`=1: dp[0][1] + dp[2][3] (3과 5 사이 + 연산)
- 최댓값: maxDp[0][1] + maxDp[2][3] = -2 + (-3) = -5
- 최솟값: minDp[0][1] + minDp[2][3] = -2 + (-3) = -5
- `split`=2: dp[0][2] - dp[3][3] (5와 8 사이 - 연산)
- 최댓값: maxDp[0][2] - minDp[3][3] = 3 - 8 = -5
- 최솟값: minDp[0][2] - maxDp[3][3] = -7 - 8 = -15
이 세 가지 분기점에서 나온 모든 최댓값 후보들(1, -5, -5) 중 가장 큰 값은 1이다. 따라서 maxDp[0][3]은 1이 되고, 이것이 최종 정답이다.
코드
import java.util.*;
class Solution {
public int solution(String arr[]) {
int[] num = new int[arr.length / 2 + 1];
boolean[] plusOp = new boolean[arr.length / 2];
int opIndex = 0;
int numCount = 0;
// 입력
for (String s : arr) {
if (s.equals("+")) {
plusOp[opIndex++] = true;
} else if (s.equals("-")) {
opIndex++;
} else {
num[numCount++] = Integer.parseInt(s);
}
}
// dp 테이블 초기화
int[][] maxDp = new int[num.length][num.length];
int[][] minDp = new int[num.length][num.length];
for (int i = 0; i < numCount; i++) {
Arrays.fill(maxDp[i], Integer.MIN_VALUE);
maxDp[i][i] = num[i];
Arrays.fill(minDp[i], Integer.MAX_VALUE);
minDp[i][i] = num[i];
}
for (int length = 1; length < numCount; length++) {
for (int start = 0; start < numCount - length; start++) {
int end = start + length;
for (int split = start; split < end; split++) {
if (plusOp[split]) { // + 연산자일 경우
// max = max + max
maxDp[start][end] = Math.max(maxDp[start][end], maxDp[start][split] + maxDp[split + 1][end]);
// min = min + min
minDp[start][end] = Math.min(minDp[start][end], minDp[start][split] + minDp[split + 1][end]);
} else { // -
// max = max + min
maxDp[start][end] = Math.max(maxDp[start][end], maxDp[start][split] - minDp[split + 1][end]);
// min = min + max
minDp[start][end] = Math.min(minDp[start][end], minDp[start][split] - maxDp[split + 1][end]);
}
}
}
}
return maxDp[0][numCount - 1];
}
}