[프로그래머스] 코딩테스트 연습 - 사칙연산(Python)

문제

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

 

입출력 예시

arrresult

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

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

프로그래머스

 

Level4 문제라서 확실히 쉽게 풀리지는 않았습니다. 이 문제는 학부수업을 들으면서 접했던 문제이기도 한데, 그 때도 풀지 못했었던 기억이 있어서, 다시 한번 이참에 제대로 정리해보려고 합니다.

 

접근할 수 있는 방법으로는 순열/조합 알고리즘을 사용하거나, DP 알고리즘으로 푸는 방법을 생각해볼 수 있습니다. 하지만, 순열/조합으로 접근하기에는 분명 시간초과가 날 것이기 때문에, DP알고리즘으로 푸는 것이 적절할 것입니다.

 

풀이를 이해한 것은 저번 학부수업에서 들었던 코드를 토대로 설명해볼게요.

이 문제에서 중요한 부분은 더하기와는 달리 빼기는 결합법칙이 성립하지 않는다는 점이에요.

예시를 살펴보죠.

위 예시의 경우엔 6개의 피연산자가 있고, 그로인해 5가지의 형태가 도출됩니다. 즉, N개의 피연산자가 있다면, N-1개의 범위 결합 형태로 묶을 수 있다는 것입니다. 다시 말해, 1개씩 묶는 형태부터 5개씩 묶는 형태까지 5개의 형태로 범위를 결합할 수 있습니다. 이 같은 형태를 통해서, 이전에 구한 값을 활용해 다음 값에도 영향을 주고 있기 때문에 DP알고리즘을 적용해야 하는 것을 분명히 알 수 있습니다.

 

그럼, 사용할 DP배열을 먼저 정의 해보겠습니다.

덧셈과 뺄셈에 따라서 DP배열이 구분되는데요

• 덧셈의 경우, 가장 큰 수 끼리 합하는 것이 최대값을 만듭니다.
• 뺄셈의 경우, 가장 큰 값에서 가장 작은 값을 빼는 경우가 최대값을 만듭니다.

이처럼, 연산자의 종류에 따라 로직을 분리할 필요가 있기 때문에, 이에 대한 각각의 DP배열을 만들어 주겠습니다.

 

 

덧셈의 경우에는 가장 큰 수끼리 합하는 것이 최대값을 만들지만, 뺄셈의 경우에는 최대값을 구하는 법이 약간 다릅니다. 뺄셈은 가장 큰 값에서 가장 작은 값을 빼는 경우가 최대값을 만들기 때문에, 우리는 연산자의 종류에 따라 로직을 분리할 필요가 있습니다. 따라서 우리는 이에 대한 각각의 DP 배열을 만들어 줄 것입니다.

MAX_DP i번째 피연산자부터 j번째 피연산자까지의 최대값을 의미하고,

MIN_DP i번째 피연산자부터  j번째 피연산자까지의 최소값을 의미합니다. 

 

 

다음은 점화식을 살펴볼게요.

위에서 설명한 것처럼,

덧셈의 경우에는 (가장 큰 수 끼리 합하는 것)이 최대값을 만들고, (가장 작은 수 끼리 합하는 것)이 최소값을 만듭니다.

뺄셈의 경우에는 (가장 큰 값)-(가장 작은 값) 인 경우가 최대값을 만들고, (가장 작은 값)-(가장 큰 값)인 경우가 최소값을 만듭니다.

여기서 i는 시작하는 피연산자의 위치, j는 마지막 지점의 피연산자의 위치 그리고  k는 기준이 되는 피연산자의 위치를 의미합니다.

 

이런식으로 0번 부터 N번까지의 최대값, 최소값을 계속 갱신해 나가다 보면, N이 구하고자 하는 값에 도달하게 됩니다. 그때 나온 최대값이 우리가 최종적으로 구하고자 하는 값이 됩니다.

점화식 만큼이나 중요한 것이 초기 DP 배열의 정의입니다. 우리는 두 가지 DP 배열을 쓰기 때문에 2개의 DP 배열을 초기화 해주어야 합니다.

 

문제에서 주어지는 arr 배열에는 피연산자와 연산자가 혼합되어 들어있습니다.

DP 배열에는 피연산자만 담아 사용하도록 하겠습니다. 이때 초기값은 최대값 DP 배열의 경우엔 -Infinity로, 최소값 DP 배열의 경우엔 Infinity로 합니다.

최대값의 경우엔 더 큰 경우 갱신이 일어나기에 항상 가장 작은 값으로 간주되는 -Infinity를, 최소값은 더 작은 경우 갱신이 일어나므로 항상 가장 큰 값으로 간주되는 Infinity를 할당합니다.

우리는 위에서 N개의 피연산자가 있다면 N-1개의 범위 결합 형태로 묶을 수 있다는 것을 확인했습니다.

 

따라서, 가장 외부에 있는 반복문은 n-1번 만큼 순회하며 값을 찾아갈 것입니다.

예시를 보면, 1개씩 묶는 범위 결합형태부터, 3개를 묶는 범위 결합 형태까지 3번 순회합니다.

 

반복문 내부에서 우리가 필요한 값은 dp 배열에서 시작하는 피연산자의 위치 i, 마지막 지점의 피연산자 위치 j 그리고 기준이 되는 피연산자의 위치 k가 필요합니다.

 

모든 계산이 끝나면, 우리가 처음에 선언했던 DP 배열의 정의에 따라 max_dp의 0번째 마지막 피연산자 위치에 최대값이 들어있게 될 것입니다.

 

아래는 전체 코드입니다.

def solution(arr):
    
    INF = int(1e9)
    min_dp = [[INF for _ in range(len(arr)//2 + 1)] for _ in range(len(arr) //2 +1)]
    max_dp = [[-INF for _ in range(len(arr)//2 + 1)] for _ in range(len(arr) //2 +1)]
    
    for i in range(len(arr) //2 + 1):
        min_dp[i][i] = int(arr[i * 2])
        max_dp[i][i] = int(arr[i * 2])
    
    for c in range(1,len(max_dp)):
        for i in range(len(max_dp) -c):
            j = i + c
            for k in range(i,j):
                if arr[k*2 + 1] == "+":
                    max_dp[i][j] = max(max_dp[i][j],max_dp[i][k] + max_dp[k+1][j])
                    min_dp[i][j] = min(min_dp[i][j],min_dp[i][k] + min_dp[k+1][j])
                elif arr[k*2 +1] =='-':
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j])
    
    return max_dp[0][-1]