코딩테스트 연습 - 사칙연산

문제 풀이 아이디어

처음에는 완전탐색을 통해 풀까도 생각했습니다만 아마 무조건 시간초과가 날 만한 사이즈의 문제입니다. DP를 활용해서 풀어보겠습니다.

최댓값과 최솟값 DP를 둘 다 만들어야!

점화식을 만들기 전에 주의할 점을 하나 언급하고 가겠습니다. 현재 우리가 구하고자 하는 값은 (0번째 수 ~ 마지막 수)를 연산한 결과 중에 가장 큰 값을 찾는 것입니다. 즉 최댓값을 DP를 통해 저장해가면서 푸는 문제라는 것을 알 수 있습니다.

하지만 우리가 연산해야 하는 연산자는 2개입니다. +와 -가 있는데요. 각각 최댓값을 구하는 메커니즘이 다릅니다.

예를 들어 여러 정수가 들어있는 배열 A와 배열 B에서 하나씩을 뽑아 (뽑힌 수를 각각 a, b 라고 합시다.) 연산하여 최댓값을 구해야 한다고 가정해봅시다. 만약 + 연산이라면 a와 b를 모두 최댓값을 뽑으면 됩니다. 하지만 - 연산의 경우 a는 최댓값을 뽑되 b는 최솟값을 뽑아야 합니다.

따라서 DP를 수행할 때 최댓값만을 구해서 저장하지 말고 2개의 저장공간을 선언해서 최댓값과 최솟값을 모두 구해나가야 합니다.

DP를 실시하는 순서

이차원 배열을 이용한 dp를 실시할 때 보통은 그냥 일반적인 이중 반복문을 사용해서 풀면 되는데요. 이 문제는 좀 다릅니다. 이 문제의 경우는 그렇게 풀게되면 점화식에서 아직 구하지 않는 dp 값을 참조하는 경우가 있기 때문입니다.

이 경우에는 f(i, j)에서 i와 j의 간격 즉 j - i가 0일 때 (초기값) 부터 점점 늘려가면서 반복문을 실시해야 합니다. 이렇게 해야지만 f(i, j)를 구할 때 필요한 f(i, i), f(i + 1, j), f(i, i + 1), f(i + 2, j) 등의 값이 이미 구해진 상태에서 dp를 실시할 수 있기 때문입니다.

코드

func solution(_ input_array:[String]) -> Int {
    // 점화식 함수
    func f(_ i: Int, _ j: Int) {
        var maxResult = Int.min
        var minResult = Int.max
        
        for x in i..<j {
            let oper = input_array[x * 2 + 1]
            switch oper {
            case "+":
                maxResult = max(maxMatrix[i][x] + maxMatrix[x + 1][j], maxResult)
                minResult = min(minMatrix[i][x] + minMatrix[x + 1][j], minResult)
            case "-":
                maxResult = max(maxMatrix[i][x] - minMatrix[x + 1][j], maxResult)
                minResult = min(minMatrix[i][x] - maxMatrix[x + 1][j], minResult)
            default:
                fatalError()
            }
        }
        
        maxMatrix[i][j] = maxResult
        minMatrix[i][j] = minResult
    }
    
    // 숫자만 골라서 배열에 넣기
    var nums = [Int]()
    for i in stride(from: 0, to: input_array.count, by: 2) {
        nums.append(Int(input_array[i])!)
    }
    
    // DP : 최댓값, 최솟값 따로
    var maxMatrix = Array(repeating: Array(repeating: 0, count: nums.count), count: nums.count)
    var minMatrix = Array(repeating: Array(repeating: 0, count: nums.count), count: nums.count)
    
    // 초기값 넣기
    for i in 0..<nums.count {
        maxMatrix[i][i] = nums[i]
        minMatrix[i][i] = nums[i]
    }
    
    // k = j - i의 값
    for k in 1..<nums.count {
        for i in 0..<nums.count {
            let j = i + k
            guard j < nums.count else { break }
            f(i, j)
        }
    }
    
    // 최대값 리턴
    return maxMatrix[0][nums.count - 1]
}