[프로그래머스 알고리즘 고득점 Kit][동적계획법(Dynamic Programming)][Java] 사칙연산

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

프로그래머스

 

 

 

1. 틀린코드

작은 영역부터 잘라서 왼쪽의 최대 최소, 오른쪽 최대 최소를 이용해 특정 영역의 최댓값을 구한다.

간격이 가장 작은 2부터 0~0 최대 최소 0~2 최대 최소 2~4 ...를 찾아가고
간격이 커지면서 0~4 4~8 .. 이렇게 범위를 늘려간다.

그렇게 되면 N^3의 시간복잡도가 나오는데 시간초과가 떴다.
복잡도를 줄이는 건 도저히 모르겠어서 의심되는 곳을 바꿔보기로 했다.

class Solution {
    public int solution(String arr[]) {
        int len = arr.length;
        int[][] max = new int[len][len];
        int[][] min = new int[len][len];

        for(int i=0; i<len; i+=2) {
            max[i][i] = Integer.parseInt(arr[i]);
            min[i][i] = Integer.parseInt(arr[i]);
        } 
        for(int gap=2; gap<len; gap+=2) {
            for(int start=0; start+gap<len; start+=2) {
                int end = start + gap;
                
                max[start][end] = Integer.MIN_VALUE;
                min[start][end] = Integer.MAX_VALUE;
                
                for(int signIdx=start+1; signIdx<end; signIdx+=2) {
                    int leftMax = max[start][signIdx-1];
                    int leftMin = min[start][signIdx-1];
                    int rightMax = max[signIdx+1][end];
                    int rightMin = min[signIdx+1][end];
                    
                    
                    int candidateMax;
                    int candidateMin;
                    
                    if(arr[signIdx].equals("+")) {
                        candidateMax = leftMax + rightMax;
                        candidateMin = leftMin + rightMin;
                    } else {
                        candidateMax = leftMax - rightMin;
                        candidateMin = leftMin - rightMax;
                    }

                    max[start][end] = Math.max(max[start][end], candidateMax);
                    min[start][end] = Math.min(min[start][end], candidateMin);
                }
            }
        }
        
        return max[0][len-1];
    }
}

병목이 가장 의심되는 부분은 문자열 연산이었다. equals를 char == 비교로 바꿔보자.

if(arr[signIdx].charAt(0) == '+') {
                        candidateMax = leftMax + rightMax;
                        candidateMin = leftMin + rightMin;
                    } else {
                        candidateMax = leftMax - rightMin;
                        candidateMin = leftMin - rightMax;
                    }

평균 시간은 줄었으나 결과는 똑같았다.
두번째 의심되는 곳은 문자열 배열이었다.
클래스 배열이기 때문에 하나의 인덱스마다 참조 접근을 하기 때문에 느릴 수 있다고 판단했다.
게다가 N^3 반복문 안에서 문자열 배열 인덱스 접근 -> 참조접근 -> charAt() 호출 -> 비교연산으로 충분히 의심할만하다.

그래서 기호 문자열을 미리 char 배열로 빼두고 다시.

 

2. 정답코드

class Solution {
    public int solution(String arr[]) {
        int len = arr.length;

        char[] ops = new char[len];

        for (int i = 1; i < len; i += 2) {
            ops[i] = arr[i].charAt(0);
        }

        int[][] max = new int[len][len];
        int[][] min = new int[len][len];

        for(int i=0; i<len; i+=2) {
            max[i][i] = Integer.parseInt(arr[i]);
            min[i][i] = Integer.parseInt(arr[i]);
        } 

        for(int gap=2; gap<len; gap+=2) {
            for(int start=0; start+gap<len; start+=2) {
                int end = start + gap;
                
                max[start][end] = Integer.MIN_VALUE;
                min[start][end] = Integer.MAX_VALUE;
                
                for(int signIdx=start+1; signIdx<end; signIdx+=2) {
                    int leftMax = max[start][signIdx-1];
                    int leftMin = min[start][signIdx-1];
                    int rightMax = max[signIdx+1][end];
                    int rightMin = min[signIdx+1][end];
                    
                    int candidateMax;
                    int candidateMin;
                    
                    if(ops[signIdx] == '+') {
                        candidateMax = leftMax + rightMax;
                        candidateMin = leftMin + rightMin;
                    } else {
                        candidateMax = leftMax - rightMin;
                        candidateMin = leftMin - rightMax;
                    }

                    max[start][end] = Math.max(max[start][end], candidateMax);
                    min[start][end] = Math.min(min[start][end], candidateMin);
                }
            }
        }
        
        return max[0][len-1];
    }
}