프로그래머스 사칙연산

https://school.programmers.co.kr/tryouts/71889/challenges

위의 문제는 총 2 개의 메모이제이션이 필요하다. 최대가 될 수 있는 값고 최소가 될 수 있는 값을 모두 기록할 필요가 있기 때문이다. 따라서 이를 위해서 Max, Min 두개의 이차원 배열을 생성했다.

문제를 푸는 과정은 다음과 같다.
1. max, min 배열 선언
- 이 배열을 생성하는데 있어서 가장 중요한 점은 사이즈이다. 초기에 풀이할 때 메모이제이션에 기록된 값을 다시 사칙 연산에서 꺼내오는 관계구조를 만들때 어떻게 생성해야 하는것인지가 중요했다. 하지만 이러한 관계를 생각해서 하면 할 수록 더욱 복잡한 로직을 필요로한다 따라서 이를 위해 가장 간단하게 식의 시작점과 끝점으로 최대값을 설정했다 따라서 해당 범위의 인덱스 두개 만으로 비지니스로직을 수행하는 것이 가능하다는 것이다. 또한 이러한 방식으로 값을 기록하기 위해서는 배열의 크기가 주어진 식의 크기와 동일한 크기를 가지는 이차원 배열이여야한다

2. 슬라이딩 윈도우 개념의 도입.

   슬라이딩 윈도우 개념은 특정 길이의 범위를 가지고 배열 내에서만 위치를 변경하는 것이다.

이를 이용하기 위해서 설정한 것은 바로 메모이제이셔의 초기화이다다. 윈도우의 범위가 하나 이거나 3개 즉 하나 혹은 두개의 연산만이 존재할 때는 최대값이 정해진다. 단순하게 해당연산을 수행하는 경우나 아니면 그 수 자체가 최댓값이다. 따라서 이점을ㅇ용해서 메모이제이션을 먼저 초기화한후 점점 윈도우의 사이즈를 늘려가면서 표를 채워나가서 결국의 MaxMemo 의 배열의 [0][array.length] 에 이 식의 최종적이 최댓값이 저장된다. 책에서 보면 해당문제를 재귀를 이용해서 풀이한경우가 많다 하지만 재귀를 이용할 경우에 메모리의 사용량이 함수의 선언만튼 늘어나게 된다 따라서 해당 방법이 더 문제를 빠르게 풀수 있는 방법이다.

import java.util.*;
class Solution {
    
    public int calculate(String head, String body, String sub){
        int h = Integer.valueOf(head);
        int s = Integer.valueOf(sub);
        int result = 0;
        if(body.equals("+")){
            result = h + s;
        }
        if(body.equals("-")){
            result = h-s;
        }
        return result;
    }
    
    public int solution(String arr[]) {
        int l = arr.length;
        
        int answer = -1;
        
        int[][] maxMemo = new int[l][l];
        int[][] minMemo = new int[l][l];
        for(int i = 0; i < maxMemo.length; i++){
            Arrays.fill(maxMemo[i], Integer.MIN_VALUE);
            Arrays.fill(minMemo[i], Integer.MAX_VALUE);

        }
        
        for(int i = 0; i< arr.length; i+=2){
            maxMemo[i][i] = Integer.parseInt(arr[i]);
            minMemo[i][i] = Integer.parseInt(arr[i]); 
        }
        
        for(int i = 0; i < arr.length-2; i+=2){
            maxMemo[i][i+2] = calculate(arr[i],arr[i+1], arr[i+2]);
            minMemo[i][i+2] = calculate(arr[i],arr[i+1], arr[i+2]);
        }
        
        for(int j = 3; j < arr.length+1; j+=2){//dnls
            int window = j;
            for(int i = 0; i<= arr.length - window; i+=2){
                for(int k = i+1; k < i + window; k+=2){
                    
                    String operator = arr[k];
                    if(operator.equals("+")){
                        if(maxMemo[i][i+window-1] < maxMemo[i][k-1] + maxMemo[k+1][i+window-1])
                            maxMemo[i][i+window-1] = maxMemo[i][k-1] + maxMemo[k+1][i+window-1];
                        

                        if(minMemo[i][i+window-1] > minMemo[i][k-1] + minMemo[k+1][i+window-1])
                        minMemo[i][i+window-1] = minMemo[i][k-1] + minMemo[k+1][i+window-1];
                    }
                    
                    if(operator.equals("-")){
                        if(maxMemo[i][i+window-1] < maxMemo[i][k-1] - minMemo[k+1][i+window-1])
                        maxMemo[i][i+window-1] = maxMemo[i][k-1] - minMemo[k+1][i+window-1];
                        if(minMemo[i][i+window-1] > minMemo[i][k-1] - maxMemo[k+1][i+window-1])
                        minMemo[i][i+window-1] = minMemo[i][k-1] - maxMemo[k+1][i+window-1];

                    }

                }
            }
        }
        
        return maxMemo[0][arr.length-1];
    }
}