[Programmers] 사칙연산

난이도 : Level 4

문제링크

• 문자열 배열 arr가 매개변수로 주어짐 : 숫자, 더하기 기호, 뺄셈 기호
• arr의 괄호를 사용하여 연산순서가 이전과 다른 연산을 할 수 있다
• 괄호 사용을 포함한 모든 연산에 대한 결과 중 최댓값을 리턴하라
• 길이 : 3 이상 201 이하 (항상 홀수)

example) 1 - 3 + 5 - 8

(((1 - 3) + 5) - 8) = -5 
((1 - (3 + 5)) - 8) = -15 
(1 - ((3 + 5) - 8)) = 1 
(1 - (3 + (5 - 8))) = 1 
((1 - 3) + (5 - 8)) = -5

 

해설

• 주어진 arr의 부분합들을 조합해서 가장 큰 최댓값을 리턴한다
• 동적계획법을 활용하여 2부터 arr의 전체길이까지 반복하면서 부분합들을 연산하고 만들어간다
  
  • 0부터 마지막 길이까지의 가장 큰 합의 값을 리턴한다
• 부분합들의 최대값 뿐만 아니라 최소값도 함께 메모이제이션이 필요하다
• 최대값을 생성하는데 최소값이 후보가 될 수 있으므로 비교 대상에 포함되야 한다
  • 괄호를 사용하여 연산 순서를 바꿀 때, 뺄셈 연산 뒤에 괄호를 사용하면 괄호안의 부호가 바뀐다
  • 괄호 앞에 뺄셈연산이 있고, 괄호 안에 최소값(마이너스 값)이 들어간다면
    • 부호가 바뀌어 최대값보다 더 큰 덧셈 연산이 발생할 수 있다

 

코드

int[][] min, max;

public int solution(String arr[]) {
    int size = arr.length/2+1;
    min = new int[size][size];
    max = new int[size][size];

    for (int i = 0; i < size; i++) {
        min[i][i] = Integer.parseInt(arr[i*2]);
        max[i][i] = Integer.parseInt(arr[i*2]);
    }

    for (int op = 2; op <= size; op++) {
        for (int i = 0; i <= size-op; i++) {
            int j = i + op - 1;
            min[i][j] = Integer.MAX_VALUE;
            max[i][j] = Integer.MIN_VALUE;
            for (int k = i; k < j; k++) {
                if (arr[k*2+1].equals("+")) {
                    min[i][j] = Math.min(min[i][j], min[i][k] + min[k+1][j]);
                    max[i][j] = Math.max(max[i][j], max[i][k] + max[k+1][j]);
                } else {
                    min[i][j] = Math.min(min[i][j], min[i][k] - max[k+1][j]);
                    max[i][j] = Math.max(max[i][j], max[i][k] - min[k+1][j]);
                }
            }
        }
    }

    return max[0][size-1];
}

• 부분합의 크기(size)를 2부터 정수 갯수만큼 만든다 
• 부분합의 첫번째 원소(i)부터 마지막 원소(j)의 인덱스 변수로 잡고 반복한다
  • 피연산자 중, 몇번째 피연산자인지 대한 인덱스를 의미하도록 정하였음.
• 이전에 생성한 부분합의 값을 활용하여 새로운 크기의 부분합을 만든다
• i~j 내의 중간 원소(k) 를 기점으로 부분합이 될 수 있는 모든 수들의 경우를 대상으로 확인한다.
• (i~k) (k+1~j) 두 부분으로 나누고 최대값, 최소값을 업데이트한다.
  • (i~k) 뒤에 있는 연산자가 + 이면,
    • 기본적인 덧셈연산으로 최대값, 최소값 갱신
  • (i~k) 뒤에 있는 연산자가 - 이면,
    • 최소값 : min(i~k) - max(k+1, j)
    • 최대값 : max(i~k) - min(k+1, j)
• 0부터 맨 마지막까지 부분합 중 가장 큰 합인 max[0][size-1]을 리턴

 

 

블로그 참고

• kamo - [Java] 프로그래머스 -사칙연산(4단계)