[프로그래머스] 사칙연산 (Swift)

DP 동적프로그래밍

["1", "-", "3", "+", "5", "-", "8"] 이런 사칙연산을 담은 문자열 배열이 주어진다.

빼기의 결합법칙에 따라 계산 결과가 달라지는 것을 고려해서, 어떤식으로 결합했을 때 이 사칙연산의 결과값이 가장 큰 지

그 최댓값을 반환하는 문제

 

접근방법

https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0

[프로그래머스] LV.4 사칙연산

좀 헤매면서 풀었는데 이 블로그의 풀이가 가장 이해하기 쉬웠다.

핵심 개념은 사칙연산을 뒤에 부터 보면서, +가 나올 때는 그냥 더하고, -가 나올 때는 -를 - 바로 뒤의 수까지만 적용할 것인지(바로 뒷 숫자는 무조건 빼야하는 수), 그 뒤에 수까지 -를 적용할 것인지 (만약 뒤에 나오는 음수의 절댓값이 앞의 수들에 비해 훨씬 클 경우 그 음수에 -를 적용하는 것이 더 큰 값을 낼 수 있으니까) 비교해서 결정한다. 는 걸 알고 풀어야 하는 문제이다.

 

이 개념을 잘 적용하면 모든 구간의 최대 최소를 저장해두어야 한다.

그래서 각 구간의 최댓값을 담은 2차원 배열 max_dp와 최솟값을 담은 2차원 배열 min_dp를 만들어 사용한다.

즉 max_dp[i][j] 는 i부터 j번째 피연산자 까지의 연산 최댓값을 저장하고 있는 것이다.

 

처음엔, 본인부터 본인까지의 연산은 본인이기 때문에 그 값을 먼저 [i][i]에 저장하고 시작한다.

그리고 나서 가장 구간이 짧은 범위부터 넓은 범위까지 계산하는 식의 DP 문제이다.

각 구간의 최댓값과 최솟값을 갱신하는 방법은 아래와 같다.

 

구간안에 있는 연산자가 +인지 -인지에 따라 달라지는데,

현재 k번째 피연산자 뒤에 있는 연산자가 +일 경우 (k는 i 부터 j 사이에 있는 피연산자이다. 한칸한칸 계산하여 비교한다.)

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] )

더하기는 별다를 것 없이 뒤에 올 값들을 더해서 비교하면 된다.

 

현재 k번째 피연산자 뒤에 있는 연산자가 -일 경우

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] )

빼기일 경우, 최댓값은 k번까지의 최댓값 - k부터j까지의 최솟값 이다. (가장 큰 것에서 가장 작은 것을 빼야 최댓값을 얻을 수 있음)

반대로 최솟값은 k번째까지의 최솟값 - k부터j까지의 최댓값이다. (가장 작은 값에서 가장 큰 값을 빼야 최솟값을 얻음)

 

지금 i~j까지의 범위는 그 전 반복문에서 그보다 작은 범위의 max_dp, min_dp의 값이 계산되었기 때문에

그 안에서의 구간의 최대최소값은 이미 다 채워져 있을 것이다.

따라서 이 과정을 반복하면 처음부터 끝까지의 범위도 계산이 되고 max_dp[0][n-1]을 출력하면 된다.

 

소스코드

import Foundation

func solution(_ input_array:[String]) -> Int
{    
    var operands:[Int] = input_array.filter { $0 != "+" && $0 != "-" }.map{ Int($0) ?? 0 }
    var n = operands.count
    
    var max_dp = Array(repeating: Array(repeating: Int.min, count: n), count: n)
    var min_dp = Array(repeating: Array(repeating: Int.max, count: n), count: n)
    
    for i in 0..<n {
        max_dp[i][i] = operands[i]
        min_dp[i][i] = operands[i]
    }
    
    for cnt in 1..<n {
        for i in 0..<n-cnt {
            var j = i+cnt
            for k in i..<j {
                var operatorr = input_array[k*2+1]
                if operatorr == "+" {
                    max_dp[i][j] = [max_dp[i][j], max_dp[i][k] + max_dp[k+1][j]].max()!
                    min_dp[i][j] = [min_dp[i][j], min_dp[i][k] + min_dp[k+1][j]].min()!
                } else {
                    max_dp[i][j] = [max_dp[i][j], max_dp[i][k] - min_dp[k+1][j]].max()!
                    min_dp[i][j] = [min_dp[i][j], min_dp[i][k] - max_dp[k+1][j]].min()!
                }
            }
        }
    }

    return max_dp[0][n-1]
}