문제 설명 및 제한사항
문제 설명
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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")
•
배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.
아이디어 및 해결 방법
•
다이나믹 프로그래밍으로 해결 가능합니다.
◦
중요한 아이디어는, 최댓값을 구하기 위해서는 덧셈 뒤에 나오는 수는 가장 커져야 하고, 뺄셈 뒤에 나오는 수는 가장 작아져야 합니다.
◦
따라서 i번째 수부터 j번째 수까지, 여러 가지 가능한 연산 결과 중 (1) 최댓값과 (2) 최솟값을 각각 저장해두어야 합니다.
◦
편의상 (i, j) 튜플을 키로 갖는 딕셔너리로 메모이제이션 합니다.
◦
M[(i, j)] : nums[i] 부터 nums[j] 까지 연산했을 때 나올 수 있는 최댓값
◦
m[(i, j)] : nums[i] 부터 nums[j] 까지 연산했을 떄 나올 수 있는 최솟값
•
DP를 위한 관계식은 아래와 같습니다.
◦
i < k <= j 인 k를 생각하여 i~j 구간이 i~k-1, k~j 의 두 구간으로 나뉜다고 하자.
◦
이 때, op[k-1]의 종류에 따라서 M[(i, j)]와 m[(i, j)]계산을 위해 기억해둘 값이 달라진다.
◦
op[k-1]이 + 인 경우,
▪
최댓값을 위해서는 M[(i, k-1)] + M[(k, j)]를 기억해둔다. (큰 값과 큰 값을 더함)
▪
최솟값을 위해서는 m[(i, k-1)] + m[(k, j)]를 기억해둔다. (작은 값과 작은 값을 더함)
◦
op[k-1]이 -인 경우,
▪
최댓값을 위해서는 M[(i, k-1)] - m[(k, j)]를 기억해둔다. (큰 값에서 작은 값을 뺌)
▪
최솟값을 위해서는 m[(i, k-1)] - M[(k, j)]를 기억해둔다. (작은 값에서 큰 값을 뺌)
◦
이제 기억해둔 값들을 가지고, 각각 그 값들의 최댓값, 최솟값을 M[(i, j)]와 m[(i, j)]에 할당하면 된다. 이를 반복한다.
코드
# M[(i, j)]
# nums[i] 부터 nums[j]까지 연산했을 때 나올 수 있는 최댓값
# m[(i, j)]
# nums[i] 부터 nums[j]까지 연산했을 때 나올 수 있는 최솟값
M, m = {}, {}
# 점화식
# i~j를 두 부분으로 분할하는 모든 k에 대해서 (k=i+1, i+2, ..., j)
# --> i~k-1 / k~j로 나뉜다고 하자
# 나올 수 있는 연산의 최댓값, 최솟값을 저장해 두어야 한다.
# ops[k-1]의 경우에 따라 나뉜다
# ops[k-1] == '-'인 경우,
# 최댓값을 위해서는 M[(i, k-1)] - m[(k, j)] 를 기억해둔다.
# 최솟값을 위해서는 m[(i, k-1)] - M[(k, j)] 를 기억해둔다.
# ops[k-1] == '+'인 경우,
# 최댓값을 위해서는 M[(i, k-1)] + M[(k, j)] 를 기억해둔다.
# 최솟값을 위해서는 m[(i, k-1)] + m[(k, j)] 를 기억해둔다.
def solution(arr):
nums = [int(x) for x in arr[::2]]
ops = [x for x in arr[1::2]]
for i in range(len(nums)):
M[(i, i)] = nums[i]
m[(i, i)] = nums[i]
for d in range(1, len(nums)):
for i in range(len(nums)):
j = i + d
if j >= len(nums):
continue
maxcandidates, mincandidates = [], []
for k in range(i+1, j+1):
if ops[k-1] == '-':
mx = M[(i, k-1)] - m[(k, j)]
mn = m[(i, k-1)] - M[(k, j)]
maxcandidates.append(mx)
mincandidates.append(mn)
else:
mx = M[(i, k-1)] + M[(k, j)]
mn = m[(i, k-1)] + m[(k, j)]
maxcandidates.append(mx)
mincandidates.append(mn)
M[(i, j)] = max(maxcandidates)
m[(i, j)] = min(mincandidates)
return M[(0, len(nums) - 1)]
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges