[프로그래머스] 사칙연산(JAVA)

코딩테스트연습(동적계획법) - 사칙연산

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

프로그래머스

문제 설명

뺄셈은 괄호를 어디에 치는가에 따라 계산결과가 달라질 수 있다.

어떤 수식이 주어졌을 때 괄호를 이용하여 뺄셈의 순서를 자유롭게 바꿔서 최댓값을 구하는 문제이다.

---

문제 풀이

생각 과정

우선 DP 문제이므로 메모이제이션을 써야겠다고 생각했고 -부호를 기준으로 뒤의 식만 변경이 되므로

주어진 수식을 뒤에서부터 계산해야겠다고 생각했다.

그리고 결국 최댓값을 구하는 문제이므로 각 연산순서마다 최댓값과 최솟값을 구하면 된다고 생각했다.

최솟값도 구해주는 이유는 최솟값이 만약 음수라면 -를 붙였을 때 양수로 바뀌므로 최대가 될 가능성이 있기 때문이다.

 

내가 구현한 방법은 이렇다.

수식을 뒤에서 부터 진행한다.

Max는 지금까지 계산한 값 중 최댓값이고

Min은 지금까지 계산한 값 중 최솟값이다.

Sum은 마지막으로 계산한 숫자 이후에 나온 양수의 합이다.

우선 + 가 나오면 해당 숫자를 Sum에 저장한다. (왜냐하면 +끼리는 모두 한 덩어리로 취급한다.)

- 가 나오면 이제 각 경우를 따져보며 Max와 Min값을 갱신한다.

Max는 -(4+12+0) 과 -4+12+0 중에 더 큰 8
Min은 -(4+12+0) 과 -(4+12)+0 중에 더 작은 -16

Sum은 사용했으므로 다시 0으로 초기화 시켜준다.

 

Max는 -(3+0-16) 과 -3+0+8 중에 더 큰 13
Min은 -(3+0+8) 과 -(3+0)-16 중에 더 작은 -19

 

과정을 반복하다 맨 첫번째 숫자에 도달하면 Max와 Min모두에 남은 Sum과 첫번째 숫자를 더해주고 마무리한다.

따라서 주어진 식의 최댓값은 14이다.

 

다 풀고보니 DP처럼 푼게 아닌것 같다...허허

---

구현

class Solution {
    public int solution(String arr[]) {
        int max = 0;
        int min = 0;
        int sum = 0;
        for (int i = 0; i < arr.length-1 ; i += 2) {	// 2계단씩 체크하기
            int num = Integer.parseInt(arr[arr.length - 1 - i]);	// 뒤에서부터 숫자 
            String pm = arr[arr.length - 2 - i];	// 연산부호
            if (pm.equals("+")) sum += num;		// +의 경우 sum에 더해준다.
            else if (pm.equals("-")) {			// -의 경우
                int temp1 = -(num + sum + min);
                int temp2 = -num + sum + max;
                int temp3 = -(num+ sum + max);
                int temp4 = -(num + sum) + min;
                max = Math.max(temp1, temp2);
                min = Math.min(temp3, temp4);
                sum = 0;
            }
        }
        return max + Integer.parseInt(arr[0]) + sum;
    }
}

---

주의점

처음 틀렸을 때 마지막 리턴 문을 아래와 같이 작성했다.

 return max + Integer.parseInt(arr[0]);

이렇게 작성하면 아래와 같은 경우에

사이에 있는 Sum값이 누락되어버리는 문제가 발생한다.

마지막에 Sum을 잊지말고 더해주자!

return max + Integer.parseInt(arr[0]) + sum;