[프로그래머스][JAVA] 1843. 사칙연산

💡 문제
사칙연산 (https://school.programmers.co.kr/learn/courses/30/lessons/1843)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

공간 복잡도와 시간 복잡도

• 공간 복잡도: 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 의미합니다. 주로 데이터 구조의 크기에 따라 결정됩니다.
• 시간 복잡도: 알고리즘이 실행되는 동안 소요되는 시간의 양을 의미합니다. 주로 입력 크기에 따라 결정됩니다.

동적 계획법(Dynamic Programming)

• 작은 부분 문제로 나누어 해결하고, 이를 통해 전체 문제를 해결하는 방법론입니다.
• 중복되는 부분 문제를 효율적으로 해결하기 위해 메모이제이션 기법을 사용합니다.
• 재귀적이거나 반복적인 방법으로 구현할 수 있습니다.

메모이제이션(Memoization)

• 이전에 계산한 값을 저장하여 재활용하여 중복 계산을 피하는 기법입니다.
• 동적 계획법과 함께 사용되어 중복 계산을 최소화하고 성능을 향상시킵니다.

---

🤓 문제 풀이

🔨 문제 설명

문제를 해결하기 위해 우선적으로 이해해야 할 점은 뺄셈 연산이 결합법칙이 성립하지 않는다는 것입니다. 이것은 괄호를 어디에 위치시키느냐에 따라 결과가 달라질 수 있다는 의미입니다.

문제를 풀기 위한 접근 방법은 가능한 모든 연산 순서를 만들어 보고, 그에 따른 결과를 계산하여 최댓값을 찾는 것입니다. 이때, 모든 연산 순서를 만들기 위해서는 연산자들의 순열을 구하면 됩니다.

순열을 구한 후에는 각 순열에 따라 계산을 수행하고, 최댓값을 찾아 반환하면 됩니다.

• 연산자 순열 생성: 빼기를 포함한 주어진 연산자들의 순열을 생성합니다. 순열을 만들 때는 재귀 함수를 사용합니다.
• 각 순열에 대해 계산: 각 연산자 순열을 가지고 식을 계산하고, 결과를 구합니다.
• 최댓값 찾기: 각 계산 결과 중 최댓값을 반환합니다.

---

🔨 접근 방법

 

---

🔨 문제 풀이 과정

• 순열 생성: 빼기와 더하기를 포함한 연산자들의 순열을 만들어냅니다. 이를 위해 재귀 함수를 사용합니다. 연산자 순열을 구성할 때는 순서가 중요하므로, 순열을 생성할 때마다 연산자를 하나씩 선택하고, 선택한 연산자를 제외한 나머지 연산자들의 순열을 재귀적으로 생성합니다.
• 순열에 대한 계산: 각 연산자 순열에 대해 식을 계산합니다. 이때, 빼기 연산은 앞의 피연산자에서 뒤의 피연산자를 빼는 방식으로 수행되므로, 순서에 주의해야 합니다. 계산 결과를 저장하고, 이 중 최댓값을 찾습니다.
• 최댓값 반환: 계산한 결과 중 최댓값을 반환합니다.

---

🔨 구현코드

12트..만..성공

import java.util.*;

class Solution {
    public int solution(String arr[]) {
        int n = arr.length;
        int[][] maxDP = new int[n][n]; // 최대값을 저장할 배열
        int[][] minDP = new int[n][n]; // 최소값을 저장할 배열

        // 각 부분의 최대값과 최소값 계산
        for (int i = 0; i < n; i++) {
            Arrays.fill(maxDP[i], Integer.MIN_VALUE);
            Arrays.fill(minDP[i], Integer.MAX_VALUE);
        }

        // 숫자와 연산자를 번갈아가며 배열에 저장
        int[] numbers = new int[(n + 1) / 2];
        char[] ops = new char[n / 2];
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                numbers[i / 2] = Integer.parseInt(arr[i]);
            } else {
                ops[i / 2] = arr[i].charAt(0);
            }
        }

        // 각 숫자는 자기 자신이 최대값이자 최소값
        for (int i = 0; i < numbers.length; i++) {
            maxDP[i][i] = numbers[i];
            minDP[i][i] = numbers[i];
        }

        // 연산자를 이용하여 모든 가능한 연산 순서를 탐색
        for (int len = 1; len < numbers.length; len++) {
            for (int i = 0; i < numbers.length - len; i++) {
                int j = i + len;
                for (int k = i; k < j; k++) {
                    char op = ops[k];
                    int a = calculate(maxDP[i][k], maxDP[k + 1][j], op);
                    int b = calculate(maxDP[i][k], minDP[k + 1][j], op);
                    int c = calculate(minDP[i][k], maxDP[k + 1][j], op);
                    int d = calculate(minDP[i][k], minDP[k + 1][j], op);
                    maxDP[i][j] = Math.max(maxDP[i][j], Math.max(a, Math.max(b, Math.max(c, d))));
                    minDP[i][j] = Math.min(minDP[i][j], Math.min(a, Math.min(b, Math.min(c, d))));
                }
            }
        }

        return maxDP[0][numbers.length - 1]; // 최대값 반환
    }

    // 두 숫자를 주어진 연산자로 연산하여 결과를 반환
    private int calculate(int a, int b, char op) {
        if (op == '+') {
            return a + b;
        } else {
            return a - b;
        }
    }
}

---

📚 풀이 보완

코드 설명

이 코드는 주어진 문자열 배열 arr에서 숫자와 연산자를 추출하여 최대값을 계산하는 동적 프로그래밍 알고리즘을 구현한 것입니다. 아래는 코드의 자세한 설명입니다:

1. solution 메서드:
   • solution 메서드는 주어진 문자열 배열 arr을 입력으로 받습니다.
   • n 변수에 배열의 길이를 저장합니다.
   • 최대값을 저장할 2차원 배열 maxDP와 최소값을 저장할 2차원 배열 minDP를 생성합니다.
   • 모든 부분에 대해 최대값과 최소값을 초기화합니다.
   • 주어진 배열에서 숫자와 연산자를 추출하여 각각 numbers와 ops 배열에 저장합니다.
   • 주어진 숫자로 maxDP와 minDP 배열을 초기화합니다.
   • 연산자를 이용하여 모든 가능한 연산 순서를 탐색하고, 각 부분에 대해 최대값과 최소값을 계산하여 maxDP와 minDP 배열에 저장합니다.
   • 최종적으로 maxDP[0][numbers.length - 1] 값인 전체 최대값을 반환합니다.
2. calculate 메서드:
   • calculate 메서드는 두 숫자와 연산자를 입력으로 받아 연산을 수행하여 결과를 반환합니다.
   • 연산자가 '+'일 경우에는 두 숫자를 더하고, '-'일 경우에는 두 숫자를 빼서 결과를 반환합니다.

이 코드는 동적 계획법을 사용하여 중복 계산을 피하고, 모든 가능한 연산 순서를 탐색하여 최대값을 효율적으로 계산합니다.

성공 코드와 실패 코드들의 주요 차이점:

1. 동적 계획법(Dynamic Programming) 사용 여부:
   • 성공 코드: 동적 계획법을 사용하여 중복 계산을 피하고 효율적으로 연산을 수행합니다.
   • 실패 코드들: 동적 계획법을 사용하지 않고 재귀적인 방식으로 모든 가능한 연산 순서를 탐색하면서 계산을 수행합니다.
2. 초기화 방식:
   • 성공 코드: 주어진 숫자를 사용하여 최대값 배열(maxDP)과 최소값 배열(minDP)을 초기화합니다.
   • 실패 코드들: 최대값 배열과 최소값 배열을 각각 Integer.MIN_VALUE와 Integer.MAX_VALUE로 초기화합니다. 이로 인해 연산 결과가 의도하지 않은 값으로 초기화되는 문제가 발생합니다.
3. 숫자와 연산자 처리:
   • 성공 코드: 주어진 배열에서 숫자와 연산자를 번갈아가며 따로 저장합니다. 이후 연산을 수행할 때 숫자 배열과 연산자 배열을 사용하여 연산을 수행합니다.
   • 실패 코드들: 주어진 배열을 직접 파싱하여 숫자와 연산자를 처리합니다. 이로 인해 연산자 처리 시 예외가 발생할 수 있습니다.
4. 최댓값 및 최솟값 계산 방식:
   • 성공 코드: 모든 가능한 연산 순서를 탐색하면서 중복 계산을 피하고 최댓값과 최솟값을 계산합니다.
   • 실패 코드들: 재귀적으로 모든 가능한 연산 순서를 탐색하면서 중복 계산을 처리하지 않고 최댓값과 최솟값을 각각 Math.max()와 Math.min()으로 구합니다.

성공 코드의 주요 로직 포인트는 다음과 같습니다:

1. 주어진 배열을 숫자와 연산자로 번갈아가며 따로 저장하여 처리합니다.
2. 동적 계획법을 사용하여 중복 계산을 피하고 모든 가능한 연산 순서를 탐색합니다.
3. 각 부분에 대해 모든 연산자의 위치를 고려하여 최댓값과 최솟값을 계산합니다.

이러한 수정을 통해 성공 코드는 정확성과 효율성 모두를 만족시킬 수 있었습니다.

---

📍 Plus+

공간 복잡도

이 알고리즘의 공간 복잡도는 주로 사용되는 데이터 구조에 의해 결정됩니다. 주요한 메모리 사용은 다음과 같습니다:

1. 2차원 배열(maxDP와 minDP): 이 배열들은 입력으로 주어진 숫자 배열에 따라 크기가 결정됩니다. 만약 입력 배열의 길이가 n이라면, 각 배열은 n x n 크기를 갖습니다. 따라서 이들의 공간 복잡도는 O(n^2)입니다.
2. 리스트(numbers와 operators): 입력 배열을 처리하는 데 사용됩니다. 각각의 리스트는 최대 n/2개의 요소를 갖을 수 있으므로, 이들의 공간 복잡도는 O(n)입니다.

따라서 이 알고리즘의 전체 공간 복잡도는 O(n^2)입니다.

시간복잡도

1. 동적 계획법(Dynamic Programming)을 사용한 최대값 및 최소값 계산: 주어진 숫자 배열의 모든 부분에 대해 최대값 및 최소값을 계산합니다. 이를 위해 2중 반복문을 사용하며, 각 부분의 길이에 비례하여 연산을 수행하므로 시간 복잡도는 O(n^3)입니다.
2. 숫자와 연산자 처리: 주어진 배열에서 숫자와 연산자를 추출하여 저장하는 데 사용됩니다. 이는 입력 배열의 길이에 선형적으로 비례하므로 시간 복잡도는 O(n)입니다.

따라서 이 알고리즘의 전체 시간 복잡도는 O(n^3)입니다.

요약

• 공간 복잡도: O(n^2)
• 시간 복잡도: O(n^3)

 

 

---

풀이 참고 로직

1. 메모이제이션 사용: 주어진 코드는 동적 계획법(Dynamic Programming)을 구현하는 데에 메모이제이션을 사용합니다. 이전 코드에서는 반복적으로 중복되는 연산을 수행하였지만, 이 코드에서는 결과를 이전에 계산한 값들을 저장하고 재활용하여 중복 계산을 피합니다. 이를 통해 시간 복잡도가 크게 개선됩니다.
2. 최소값과 최대값 분리: 주어진 코드에서는 최대값과 최소값을 계산하는 함수를 따로 구현하여 메모이제이션을 적용합니다. 이를 통해 중복 계산을 최대한 줄이고, 각각의 최대값과 최소값을 계산하여 반환합니다.
3. 재귀 호출 범위: 주어진 코드에서는 재귀 호출 범위를 더욱 정확하게 지정하여 불필요한 연산을 최소화합니다. 예를 들어, 재귀 호출에서 시작 지점과 끝 지점을 정확하게 지정하여 해당 범위에서만 연산을 수행합니다.