220318 - 사칙연산
◾ 사칙연산 : 프로그래머스 LEVEL 4
문제
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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. 프로그램
- min_max, sum_value 선언 및 초기화
- min_max : 해당 단계에서의 최소값, 최대값 리스트
- sum_value :
+
연산으로 진행된 값의 합
- 식의 뒤부터 차례로 계산 진행
+
인 경우 : 덧셈의 경우 결합 법칙이 적용되므로 추가적인 연산이 필요없다.-
인 경우 : 해당 단계에서 계산되는 최소값, 최대값을 계산한다.- 최소값
- -(sum_value(해당 단계까지의 합) + temp_max(이전 단계까지의 최대값))
- -sum_value(해당 단계까지의 합) + temp_min(이전 단계까지의 최소값)
- 최대값
- -(sum_value(해당 단계까지의 합) + temp_min(이전 단계까지의 최소값))
- -temp_value(해당 단계의 값) + (sum_value(해당 단계까지의 합) - temp_value(해당 단계의 값)) + temp_max(이전 단계까지의 최대값)
- 최소값
숫자
인 경우 : sum_value에 값을 더한다.
- 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
Author And Source
이 문제에 관하여(220318 - 사칙연산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@skarb4788/220318-사칙연산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)