[코딩테스트] Java 사칙연산

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

해당 문제는 결합법칙을 무시한 채 최대 값을 구하기 위한 문제입니다. - 연산에서는 왼쪽 값은 최댓값, 오른쪽 값은 최솟값이 되어야 최대값이 되고, + 연산에서는 두 값 모두 최대 값이 되어야 합니다. 이를 통해 dpMax 배열과 dpMin 배열을 통해 문제를 풀었습니다.

소스코드

class Solution {
        public int solution(String[] arr) {
            int n = arr.length / 2 + 1; // 숫자의 개수
            int[][] dpMax = new int[n][n];
            int[][] dpMin = new int[n][n];

            // 숫자 초기화
            for (int i = 0; i < n; i++) {
                dpMax[i][i] = Integer.parseInt(arr[i * 2]);
                dpMin[i][i] = Integer.parseInt(arr[i * 2]);
            }

            // 구간 길이
            for (int len = 1; len < n; len++) {
                for (int i = 0; i < n - len; i++) {
                    int j = i + len;
                    dpMax[i][j] = Integer.MIN_VALUE;
                    dpMin[i][j] = Integer.MAX_VALUE;

                    // i부터 j까지 연산자에 대한 분할 계산
                    for (int k = i; k < j; k++) {
                        String operator = arr[k * 2 + 1];
                        int maxLeft = dpMax[i][k];
                        int minLeft = dpMin[i][k];
                        int maxRight = dpMax[k + 1][j];
                        int minRight = dpMin[k + 1][j];

                        if (operator.equals("+")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
                        } else if (operator.equals("-")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
                        }
                    }
                }
            }

            return dpMax[0][n - 1]; // 전체 구간의 최댓값 반환
        }
    }

코드 설명

• int n = arr.length / 2 + 1; // 숫자의 개수 int[][] dpMax = new int[n][n]; int[][] dpMin = new int[n][n];
  • n: 숫자의 개수. 연산자는 숫자보다 항상 하나 적으므로, 전체 배열 길이의 절반(arr.length / 2)에 1을 더해 계산합니다.
  • dpMax[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최대값을 저장합니다.
  • dpMin[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최소값을 저장합니다.
• for (int i = 0; i < n; i++) { dpMax[i][i] = Integer.parseInt(arr[i * 2]); dpMin[i][i] = Integer.parseInt(arr[i * 2]); }
  
  • 각 숫자는 연산 없이 자기 자신이므로, dpMax[i][i]와 dpMin[i][i]를 해당 숫자로 초기화합니다.

for (int len = 1; len < n; len++) {
    for (int i = 0; i < n - len; i++) {
        int j = i + len;
        dpMax[i][j] = Integer.MIN_VALUE;
        dpMin[i][j] = Integer.MAX_VALUE;

• len: 현재 계산하려는 구간의 길이. 길이가 1부터 시작하여, 점차 늘어나며 모든 가능한 구간을 탐색합니다.
• i: 구간의 시작점.
• j: 구간의 끝점. 구간 길이가 len이므로, j = i + len으로 계산.

for (int k = i; k < j; k++) {
    String operator = arr[k * 2 + 1];
    int maxLeft = dpMax[i][k];
    int minLeft = dpMin[i][k];
    int maxRight = dpMax[k + 1][j];
    int minRight = dpMin[k + 1][j];

• k: 구간을 분할하는 기준점.
  • arr[k * 2 + 1]에서 연산자(+, -)를 가져옵니다.
  • k를 기준으로 왼쪽(i에서 k)과 오른쪽(k+1에서 j)의 최대/최소값을 가져옵니다.
    • maxLeft, minLeft: 왼쪽 구간 최대/최소값.
    • maxRight, minRight: 오른쪽 구간 최대/최소값.

if (operator.equals("+")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
} else if (operator.equals("-")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
}

• 연산자에 따라 결과를 계산
  • + 연산: 양쪽 구간의 최대/최소값을 더합니다.
  • - 연산: 왼쪽 최대값에서 오른쪽 최소값을 빼거나, 왼쪽 최소값에서 오른쪽 최대값을 뺍니다.
• 계산 결과를 갱신하며, dpMax[i][j]는 가능한 최대값, dpMin[i][j]는 가능한 최소값을 유지합니다.
• return dpMax[0][n - 1];
  • dpMax[0][n-1]: 입력 배열 전체(0번째 숫자부터 마지막 숫자까지)의 가능한 최대값을 반환합니다.