문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/1843#
풀이 과정
첫번째 시도
이 문제는 괄호의 위치에 따라 숫자 앞의 기호가 -여도 최종적으로는 더해질 수 있고, +여도 최종적으로는 빼질 수 있다.
다만, 이렇게 부호가 변환되려면 앞쪽에 -가 있어야 한다. 또한, 그 -와 현재 부호 사이에 있는 모든 수들은 +-가 바뀐다. 따라서 이를 고려해서 -이후에 괄호를 추가할지 여부(부호를 변경할 지 여부)를 선택해야 한다.
앞에서부터 하나씩 수를 추가했다. 추가할때마다 만약 이전에 -가 있었으면, 괄호를 이용해 부호를 바꿀 수 있다. 이런 경우의 수를 검토해서 수를 추가할 때마다 마지막에 괄호가 없는 경우의 최댓값, 괄호가 있는 경우의 최댓값을 각각 저장했다.(마지막에 괄호가 있어야만 부호바꾸기가 적용이 가능하므로 별도로 계산)
class Solution {
public int solution(String arr[]) {
int answer = -1;
int length = arr.length / 2 + 1;
int[][] result = new int[length][2];
result[0][0] = Integer.parseInt(arr[0]);
result[0][1] = -200000;
for(int i = 1; i < length; i++){
int n = Integer.parseInt(arr[2 * i]);
int max = Math.max(result[i - 1][0], result[i - 1][1]);
if(arr[2 * i - 1].equals("+")){
result[i][0] = max + n;
result[i][1] = result[i - 1][1] - n;
} else {
result[i][0] = max - n;
result[i][1] = Math.max(result[i][0], result[i - 1][1] + n);
}
}
return Math.max(result[length - 1][0], result[length - 1][1]);
}
}위 코드는 일부 테스트만 통과했다(공개된 테스트는 모두 통과했다). 모든 케이스를 커버하지는 못하는 로직이라는 생각이 들었다.
최종 풀이
위 코드는 괄호가 중첩으로 들어가는 경우를 고려하지 못한다.
["5", "-", "3", "-", "1", "+", "2", "-", "4"]의 경우, 5 - (3 - (1 + 2) - 4) = 9가 최댓값이 되는데, 위 코드로는 5가 나온다.
이런 경우를 해결하기 위해서는, 단순히 수식을 앞에서부터 계산하는게 아니라, 수식을 연속적으로 분할해서 계산할 필요가 있다고 생각했다.
https://school.programmers.co.kr/learn/courses/30/lessons/12942 문제와 유사하다.
먼저 아래와 같이 숫자들을 분할했다.
1. 숫자가 하나인 경우
맨 윗줄에는 먼저 5, 3, 1, 2, 4를 각각 저장한다.
2. 숫자가 둘인 경우
두번째 줄에는 5, 3은 사이에 -가 있으므로 5 - 3 = 2를 저장한다.
같은 방식으로 3, 1에는 2,
1, 2에는 3,
2, 4에는 -2를 저장한다.
3. 숫자가 셋인 경우
3번째 줄에는 3개의 숫자가 있는데, 계산 순서에 따라 결과가 달라질 수 있다. 이때 각 칸마다 최소값과 최대값을 저장한다. 최소값을 저장하는 이유는 최소값을 빼는게 최댓값을 더하는것보다 더 좋을때가 있을 수 있기 때문이다.
3개의 수의 연산결과들을 구하는 방법을 5, 3, 1의 경우로 예시를 들면
5, 3의 결과에 1을 뺀값과 5에서 3, 1의 결과를 뺀 값이 나올 수 있는 결과들이다. 각각 1, 3이므로 최댓값은 3, 최소값은 1이 된다. 따라서 3, 1을 저장한다.
같은 방식으로 3, 1, 2에는 각각 4, 0
1, 2, 4에는 -1, -1을 저장한다.
4. 숫자가 넷 이상인 경우
숫자 4개 이상을 연산하는것은 좀더 복잡하다. 5, 3, 1, 2를 예시로 들면
처음에는 5에서 3, 1, 2의 결과를 빼고, 그다음 5, 3, 1에서 2를 빼면 될거라고 생각했다. 하지만 위 두가지로는 충분하지 않았다.
다음 두가지 경우가 더 있다.
5에서 3을 빼고, 1, 2의 결과를 빼는 경우
5, 3의 결과에서 1을 빼고, 2를 더하는 경우
위 네가지 경우를 계산하면 (1, 5), (1, -1), (-1, -1), (3, 3)으로 이론상 6가지 경우가 나온다(예시의 경우 중복이 존재해서 경우가 줄었다).
위 네가지 경우를 일반화하면, 먼저 마지막에 계산할 숫자를 하나 고른후, 나머지 숫자들은 모두 계산한다(숫자 하나를 제거하면 총 숫자의 개수가 줄어들기 때문에, 현재 계산할 칸보다 위에 있는 결과들을 이용해 계산이 가능하다). 그리고 고른 숫자 앞의 숫자들을 계산한 값 + or - 고른 숫자 + or - 고른 숫자 뒤의 숫자들을 계산한 값을 마지막으로 계산하면 된다.
3개의 숫자를 연산하므로 연산순서에 따라 값이 달라질 수 있고(만약 맨 앞의 숫자나 맨뒤의 숫자를 택하면 2개를 연산하므로, 이경우에는 고려할 필요가 없다), 각 칸마다 2개의 값이 저장되므로 이로 인해 여러가지 계산결과가 나올 수 있다. 모든 결과를 계산한 후 최대, 최소를 골라 저장하면 된다.
위의 예시에서
5에서 3, 1, 2의 결과를 빼는 경우 -> 5를 선택
5에서 3을 빼고, 1, 2의 결과를 빼는 경우 -> 3을 선택
5, 3의 결과에서 1을 빼고, 2를 더하는 경우 -> 1을 선택
5, 3, 1에서 2를 빼는 경우 -> 2를 선택한 경우이다.
위 과정을 반복하면 최종 결과를 얻을 수 있다.
최종 코드
class Solution {
public int solution(String arr[]) {
int answer = -1;
int length = arr.length / 2 + 1;
int[][][] result = new int[length + 1][length + 1][2];
for(int i = 0; i < length; i++){
result[1][i][0] = Integer.parseInt(arr[2 * i]);
result[1][i][1] = Integer.parseInt(arr[2 * i]);
}
for(int i = 2; i <= length; i++){
for(int j = 0; i + j <= length; j++){
int min = 1000000;
int max = -1000000;
for(int k = 0; k < i; k++){
int sign1 = getSign(arr, 2 * (j + k) - 1, k == 0);
int sign2 = getSign(arr, 2 * (j + k) + 1, k == i - 1);
int num1 = result[k][j][0];
int num2 = result[k][j][1];
int abs = Math.max(result[i - k - 1][j + k + 1][0], -result[i - k - 1][j + k + 1][1]);
switch(2 * sign1 + sign2){
case 3:
num1 += result[1][j + k][0] + result[i - k - 1][j + k + 1][0];
num2 += result[1][j + k][1] + result[i - k - 1][j + k + 1][1];
break;
case 1:
num1 += result[1][j + k][0] - result[i - k - 1][j + k + 1][1];
num2 += result[1][j + k][1] - result[i - k - 1][j + k + 1][0];
break;
case -1:
case -3:
num1 += -result[1][j + k][0] + abs;
num2 += -result[1][j + k][1] - abs;
break;
default:
break;
}
if(max < num1) {
max = num1;
result[i][j][0] = max;
}
if(min > num2) {
min = num2;
result[i][j][1] = min;
}
}
}
}
return result[length][0][0];
}
private int getSign(String[] arr, int n, boolean pass){
if(pass || n < 0 || n >= arr.length) return 1;
if(arr[n].equals("+")) return 1;
return -1;
}
}위의 그림의 자료구조를 2차원 배열로 표현했다. 그림의 왼쪽 맨위는 `(1, 0)`, 그 오른쪽은 `(1, 1)`, 그리고 두 요소 아래에 있는 (5, 3)은 `(2, 0)`에 저장했다. 여기서 배열의 0번째 줄을 비워둔 이유는 **4. 숫자가 넷 이상인 경우** 에서 숫자를 고를때, 맨 앞이나 맨뒤를 고를 경우 2개의 숫자만 연산하지만, 맨위를 비워두면 이 경우에도 3개의 숫자를 연산하게 할 수 있다.(맨 앞을 고르면 고른 숫자 앞에 더미숫자(0)가 있게되고 맨뒤를 고르면 고른 숫자 뒤에 더미숫자(0)이 있게 된다)
자료구조는 2차원 배열이지만 코드를 보면 result가 3차원 배열로 되어 있는데, 각 칸에 최대, 최소 2개의 값을 저장해야 하기 때문이다. 마지막 dimension의 0번 요소가 최대, 1번 요소가 최소이다.
switch문을 이용해 3개의 수를 연산할 때 부호에 따라 최대값과 최소값을 계산했다. num1이 되대값, num2가 최소값이다.
getSign()을 보면 pass조건이 true일 경우, 무조건 1을 반환하도록(+로 판정하도록)했다.
이렇게 한 이유는 위 예시에서 그림 위에서 2번째 줄 왼쪽에서 3번째 칸에 있는 1, 2를 계산할 때, 실제 결과는 1 + 2 = 3이 되어야 하는데, 로직상 2개의 숫자를 연산할 때부터 숫자 하나를 고른 후, 나머지 숫자들을 연산하고, 최종 연산하도록 되어있다.
이때 1을 고르면, 0번째 줄에 있는 0과 1과 2를 연산하게 된다. 그런데 1 앞에 -가 있으므로 0 - 1 + 2 = 1이 되어서 원하는 결과와 다른 결과가 나온다. 이를 방지하기 위해 맨 앞을 고를 경우, 그 숫자 앞에 있는 연산기호는 무조건 +이 되게 했다.
