[프로그래머스] 사칙연산 - Java

 

코딩테스트 연습 - 사칙연산

문제 설명

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

• ((1 - 5) - 3) = -7
• (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

• (((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

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
  • arr의 길이는 항상 홀수입니다.
  • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
  • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

---

입출력 예

arr	result
["1", "-", "3", "+", "5", "-", "8"]	1
["5", "-", "3", "+", "1", "+", "2", "-", "4"]	3

입출력 예시

입출력 예 #1
위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.

입출력 예 #2
(5-(3+((1+2)-4))) = 3 입니다.

---

풀이

모든 경우를 다 계산하여 최댓값을 찾기에는 효율성 문제에서 걸릴 것이라 생각해서 dp를 떠올리긴 했지만, 정확한 점화식을 세우는데 어려움을 겪었다. 다른 분의 코드를 참고하여 학습하고, 습득할 수 있었다.

[Java] 찾아라 프로그래밍 마에스터 (사칙 연산)



상황에 따라 각기 다른 점화식을 세워서 합쳐져야하는 게 핵심인데, 다음과 같은 규칙을 발견해야했다.

a, b라는 식이 있다고 할 때,

a + b가 최댓값이 되려면 a는 나올 수 있는 값 중 최댓값이 되어야 하고, b는 나올 수 있는 값 중 최댓값이 되어야 한다.

a - b가 최댓값이 되려면 a는 나올 수 있는 값 중 최댓값이 되어야 하고, b는 나올 수 있는 값 중 최댓값이 되어야 한다.

 

이번엔 a, b, c의 경우를 생각해보자.

a - (b + c)가 최댓값이 되려면 앞에서처럼 a는 최댓값, (b+c)는 최솟값이 되어야 한다. b+c가 최솟값이 되기 위해서는 b와 c는 각 식에서 나올 수 있는 최솟값이 되어야한다.

a - (b - c)가 최댓값이 되려면 마찬가지로 (b-c)가 최솟값이 되어야 한다. b-c가 최솟값이 되기 위해서는 b는 나올 수 있는 값 중 최솟값이 되어야 하고, c는 나올 수 있는 값중 최댓값이 되어야 한다.

 

정리하자면 다음과 같다.

(a + b) -> (max + max)

(a - b) -> (max - min)

-(a + b) -> -(min + min)

-(a - b) -> -(min - max)

 

이러한 규칙을 고려한 dp 풀이가 필요했던 문제였으며, 상세 코드는 아래와 같다.

 

코드

public class Solution {

    private int numbers[];
    private String operations[];
    private int dp[][][];

    public int solution(String arr[]) {
        int n = arr.length / 2;

        dp = new int[2][200][200];
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                // dp[0]은 최댓값, dp[1]은 최솟값
                dp[0][i][j] = Integer.MIN_VALUE;
                dp[1][i][j] = Integer.MAX_VALUE;
            }
        }

        numbers = new int[n + 1];
        operations = new String[n];

        for (int i = 0; i < arr.length; i++) {
            if (i % 2 == 0) {
                numbers[i / 2] = Integer.parseInt(arr[i]);
                continue;
            }
            operations[i / 2] = arr[i];
        }

        return calculate(0, 0, n);
    }

    private int calculate(int flag, int start, int end) {
        // start == end인 경우는 숫자 하나만 선택된 경우이므로 자기 자신을 리턴
        if (start == end) {
            dp[flag][start][end] = numbers[start];
            return dp[flag][start][end];
        }

        // 이미 계산했었던 경우, 기존에 계산된 값 사용
        if (visited(flag, start, end)) {
            return dp[flag][start][end];
        }

        // 방문 체크
        dp[flag][start][end] = 0;

        int result = flag == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;

        // 최댓값을 구해야할 때 flag = 0
        if (flag == 0) {
            for (int mid = start; mid < end; mid++) {
                if (operations[mid].equals("-")) {
                    // a - b가 최댓값이 되는 조건 -> a는 최댓값, b는 최솟값
                    result = Math.max(result, calculate(0, start, mid) - calculate(1, mid + 1, end));
                    continue;
                }
                // a + b가 최댓값이 되는 조건 -> a, b 둘 다 최댓값
                result = Math.max(result, calculate(0, start, mid) + calculate(0, mid + 1, end));
            }
        }

        // 최솟값을 구해야할 때 flag = 1
        if (flag == 1) {
            for (int mid = start; mid < end; mid++) {
                if (operations[mid].equals("-")) {
                    // -(a - b)가 최댓값이 되는 조건 -> a는 최솟값, b는 최댓값
                    result = Math.min(result, calculate(1, start, mid) - calculate(0, mid + 1, end));
                    continue;
                }
                // -(a + b)가 최댓값이 되는 조건 -> a, b, 둘 다 최솟값
                result = Math.min(result, calculate(1, start, mid) + calculate(1, mid + 1, end));
            }
        }

        dp[flag][start][end] = result;
        return dp[flag][start][end];
    }

    private boolean visited(int flag, int start, int end) {
        // 현재값이 초기값과 동일하지 않으면 이미 방문한 경우임
        // flag = 0일 때는 초기값이 Integer.MIN_VALUE;
        // flag = 1일 때는 초기값이 Integer.MAX_VALUE;
        return dp[flag][start][end] != Integer.MIN_VALUE && dp[flag][start][end] != Integer.MAX_VALUE;
    }
}