[프로그래머스 Lv4/파이썬] 사칙연산(DP)

 

[프로그래머스 Lv4/파이썬] 사칙연산(DP)

문제 설명

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

예를 들어 식 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

위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.

입출력 예 #2

(5-(3+((1+2)-4))) = 3 입니다.

 

 

---

[다른 사람의 풀이 보고 배우기]

※ 풀이 전략

-

다이나믹 프로그래밍으로 해결 가능합니다.
중요한 아이디어는, 최댓값을 구하기 위해서는 덧셈 뒤에 나오는 수는 가장 커져야 하고, 뺄셈 뒤에 나오는 수는 가장 작아져야 합니다.
따라서 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)]

 

※ 중요 포인트

-

코딩테스트에서 만났다면 DP인지도 몰랐을 수도 있겠다 싶다. 

-

구하고자 하는 것을

'(0~n-1) 구간의' 최대, 최소 값 으로 구체화해서 생각해야만,

그제서야 (0~1)구간의 최대,최소값 과 같이 작은 부분으로 나누어 생각할 수 있게 될 것 같다.

 

 

 

※  풀이 출처

https://www.ai-bio.info/programmers/1843

[프로그래머스] 사칙연산 Python 파이썬 해설 (Level 4) - 이도훈

 

---

[다른 사람의 풀이 보고 직접 풀어보기]

- 의외로, 아이디어를 이해하니까 구현 자체는 쉬웠다. 한 15분 걸렸던 것 같다. 

def solution(arr):
    answer = -1
    # DP: 구하고자 하는 것: 0~n-1의 최댓값 구하기
    # 0~k 의 최댓값 + k+1~n-1의 최댓값 들 중, 최댓값이 구하는 값

    # 초기값
    nums = arr[::2]
    ops = arr[1::2]
    ln = len(nums)
    lo = len(ops)

    # 메인
    max_sum = dict()
    min_sum = dict()
    for i in range(ln):
        max_sum[(i, i)] = int(nums[i])
        min_sum[(i, i)] = int(nums[i])

    for d in range(1, lo + 1):
        for i in range(ln - 1):
            j = i + d

            if j >= ln:  # j가 index 범위 넘어가면 예외 처리
                continue

            max_part = []
            min_part = []
            for k in range(i, j):
                if ops[k] == '+':
                    max_num = max_sum[(i, k)] + max_sum[(k+1, j)]
                    min_num = min_sum[(i, k)] + min_sum[(k+1, j)]
                    max_part.append(max_num)
                    min_part.append(min_num)
                if ops[k] == '-':
                    max_num = max_sum[(i, k)] - min_sum[(k+1, j)]
                    min_num = min_sum[(i, k)] - max_sum[(k+1, j)]
                    max_part.append(max_num)
                    min_part.append(min_num)
            max_sum[(i, j)] = max(max_part)
            min_sum[(i, j)] = min(min_part)
    return max_sum[(0, ln - 1)]