220318 - 사칙연산

◾ 사칙연산 : 프로그래머스 LEVEL 4

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

문제

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.

예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

• ((1 - 5) - 3) = -7
• (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

• (((1 - 3) + 5) - 8) = -5
• ((1 - (3 + 5)) - 8) = -15
• (1 - ((3 + 5) - 8)) = 1
• (1 - (3 + (5 - 8))) = 1
• ((1 - 3) + (5 - 8)) = -5

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.

문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

---

입력

• arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
  • arr의 길이는 항상 홀수입니다.
  • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
  • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

출력

• 서로 다른 연산순서의 계산 결과 중 최댓값

입출력 예

arr	result
["1", "-", "3", "+", "5", "-", "8"]	1
["5", "-", "3", "+", "1", "+", "2", "-", "4]	3

---

◾ 풀이

1. 해설

• 동적 계획법을 통해 최대값을 구해갈 수 있다.
  • a + b + c - e + f - g - h + ... 이 식은 아래와 같이 구할 수 있다.
  • a + [+ b + c - e + f - g - h + ...]의 최대값
  • a + [+ b + [+ c - e + f - g - h + ...]의 최대값]의 최대값
  • a + [+ b + [+ c + [- e + f - g - h + ...]의 최대값]의 최대값]의 최대값
  • ...
• 식의 뒤부터 각 단계에서의 최대값, 최소값을 계산해나가면 전체 식의 최대값을 찾을 수 있다.

---

2. 프로그램

1. min_max, sum_value 선언 및 초기화
   • min_max : 해당 단계에서의 최소값, 최대값 리스트
   • sum_value : + 연산으로 진행된 값의 합
2. 식의 뒤부터 차례로 계산 진행
   • +인 경우 : 덧셈의 경우 결합 법칙이 적용되므로 추가적인 연산이 필요없다.
   • -인 경우 : 해당 단계에서 계산되는 최소값, 최대값을 계산한다.
     • 최소값
       • -(sum_value(해당 단계까지의 합) + temp_max(이전 단계까지의 최대값))
       • -sum_value(해당 단계까지의 합) + temp_min(이전 단계까지의 최소값)
     • 최대값
       • -(sum_value(해당 단계까지의 합) + temp_min(이전 단계까지의 최소값))
       • -temp_value(해당 단계의 값) + (sum_value(해당 단계까지의 합) - temp_value(해당 단계의 값)) + temp_max(이전 단계까지의 최대값)
   • 숫자인 경우 : sum_value에 값을 더한다.
3. sum_value + min_max[1](최대값) 반환

# 코드
def solution(arr):
    min_max = [0, 0]
    sum_value = 0
    for idx in range(len(arr) - 1, -1, -1):
        if arr[idx] == '+':
            continue
        elif arr[idx] == '-':
            temp_min, temp_max = min_max
            min_max[0] = min(-(sum_value + temp_max), -sum_value + temp_min)
            temp_value = int(arr[idx+1])
            min_max[1] = max(-(sum_value+temp_min), -temp_value+(sum_value-temp_value) + temp_max)
            sum_value = 0
        else:
            sum_value += int(arr[idx])
            
    answer = sum_value + min_max[1]

    return answer