[프로그래머스/Java] 사칙연산(DP 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 동적계획법(DP) 파트에 해당하는 '사칙연산' 문제를 자바로 풀어보았다.

https://school.programmers.co.kr/learn/courses/30/lessons/1843

프로그래머스

 

 

 이 문제는 DP 문제이기 때문에 이를 어떻게 활용할지에 대해서 가장 고민한 것 같다. 고민 끝에 결정한 방법은 l을 괄호를 여는 쪽, r을 괄호를 닫는 쪽으로 두고, dp[l][r]에 그 괄호 속 결과를 저장하는 것이었다. 처음에는 dp 배열로 2차원 배열을 하나만 사용했다. 최댓값을 찾는 문제이기에 모든 파트의 최댓값을 기록했던 것이다. 하지만 문제 특성상 어떤 부분은 최댓값이 되어야 하고 어떤 부분은 최솟값이 되어야 전체가 최댓값이 될 수 있다. (더해주는 부분은 최댓값이어야 하고, 빼주는 부분은 최솟값이어야 한다.) 따라서 mins와 maxs 배열을 각각 만들어주고, 각각을 찾는 find_min과 find_max 메서드도 각각 만들어주어서 결괏값을 구했다. 그리고 l과 r이 같은 경우는 괄호 안에 숫자 하나만 있다는 것이기 때문에, 미리 그 위치에 해당하는 값을 int값으로 변환하여 저장해두었다. 

 그리고 재귀함수와 반복문을 반복했다. 연산자를 기준으로 이동하면서 연산자 바로 앞 쪽 모든 element에 괄호를 씌우고, 바로 뒤 모든 element에 괄호를 씌우면서 최댓값/최솟값을 찾아가는 방법을 사용했다. 만약 최댓값을 찾고 있는데 연산자가 '+'라면 앞쪽과 뒤쪽 모두 최댓값이 되어야 연산 결과도 최댓값이 되기 때문에 둘 모두 find_max 함수로 다시 들어간다. 연산자가 '-'인 경우는 앞쪽 값은 최댓값, 뒤쪽값은 최솟값이 되어야 하므로, 앞쪽은 find_max를 뒤쪽은 find_min을 사용한다. 최솟값을 찾고 있는 경우는 반대이다. 이렇게 주어진 범위 안에서 괄호를 이동시키며 최댓값을 찾아 리턴한다.

import java.util.*;

class Solution {
    final int MIN_TRASH = Integer.MAX_VALUE;
    final int MAX_TRASH = Integer.MIN_VALUE;
    
    public int find_max(String[] arr, int[][] mins, int[][] maxs, int l, int r) {
        if (l > r) return 0;
        if (maxs[l][r] != MAX_TRASH) return maxs[l][r];
        
        int m = MAX_TRASH;
        for (int i = l+1; i < r; i+=2) {
            int cur = find_max(arr, mins, maxs, l, i-1);
            if (arr[i].equals("+")) cur += find_max(arr, mins, maxs, i+1, r);
            else cur -= find_min(arr, mins, maxs, i+1, r);
            
            if (cur > m) m = cur;
        }
        
        return maxs[l][r] = m;
    }
    
    public int find_min(String[] arr, int[][] mins, int[][] maxs, int l, int r) {
        if (l > r) return 0;
        if (mins[l][r] != MIN_TRASH) return mins[l][r];
        
        int m = MIN_TRASH;
        for (int i = l+1; i < r; i+=2) {
            int cur = find_min(arr, mins, maxs, l, i-1);
            if (arr[i].equals("+")) cur += find_min(arr, mins, maxs, i+1, r);
            else cur -= find_max(arr, mins, maxs, i+1, r);
            
            if (cur < m) m = cur;
        }
        
        return mins[l][r] = m;
    }
    
   
    public int solution(String arr[]) {
        int len = arr.length;
        int mins[][] = new int[len][len];
        int maxs[][] = new int[len][len];
        for (int i = 0; i < len; i++) {
            Arrays.fill(mins[i], MIN_TRASH);
            Arrays.fill(maxs[i], MAX_TRASH);
            if (i % 2 == 0) {
                mins[i][i] = Integer.parseInt(arr[i]);
                maxs[i][i] = mins[i][i];
            }
        }
        return find_max(arr, mins, maxs, 0, len-1);
    }
}

 

 

 다 풀고 너무 복잡한 풀이인 것 같아 마음에 들지 않았는데, 다른 분들의 풀이도 비슷한 접근법과 코드를 가진 걸 보니 이게 최선인 것 같다. 더 나은 풀이를 한 번 더 고민해봐야겠다.