[프로그래머스] Swift - 연속 펄스 부분 수열의 합

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

프로그래머스

 

2023.08.03 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

어떤 수열이 주어지고 해당 수열의 부분 수열에 펄스 수열을 곱하고 더한 값이 최대인 경우를 구하는 문제입니다.

펄스 수열이란 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.

 

펄스 수열이 [1, -1, 1, -1, ...] 순서인 경우와 [-1, 1, -1, 1] 순서인 경우로 나눌 수 있습니다.

 

문제에서 부분 수열에 펄스 수열을 곱하라고 하지만 사실 전체 수열에 미리 펄스 수열을 곱하고 다음 작업을 진행해도 같은 결과가 나옵니다.

펄스 수열이라는 것이 결국 1, -1로 이루어져 있기 때문에 곱했을 때 배열 요소의 부호만 바꾸는 역할을 하기 때문입니다.

 

[2, 3, -6, 1, 3, -1, 2, 4] 이 주어진 배열이라면 미리 2종류의 펄스 수열을 곱해서 준비합니다.

1로 시작하는 펄스 수열을 곱한 값: [2, -3, -6, -1, 3, 1, 2, -4]

-1로 시작하는 펄스 수열을 곱한 값: [-2, 3, 6, 1, -3, -1, -2, 4]

 

이제 이 두개의 수열(배열)의 부분 수열 합의 최댓값을 구하는 문제로 바뀌었습니다. (펄스 수열을 고려할 필요가 사라짐)

 

배열의 부분 배열의 합의 최댓값을 구하는 방법에는 여러가지가 있습니다.

그중에서 시간 복잡도가 가장 좋은 동적 계획법 DP를 사용했습니다.

 

DP

우선 부분 수열의 합의 최댓값을 기록할 dp 배열을 만듭니다.

dp[index] 는 index의 위치를 끝 인덱스로 하는 부분배열의 원소합의 최댓값을 의미합니다.

arr = [2, -3, -6, -1, 3, 1, 2, -4] 가 주어진 배열일 때

위의 예제에서 dp[0]은 0번째 인덱스가 끝인 서브 배열인 [2]의 합은 2이기 때문에 d[0] = 2가 됩니다.

index가 1인 경우에는 dp[0]이 0번째 인덱스를 끝으로 가지는 부분 수열 합의 최댓값이기 때문에 dp[0] + arr[1]과 arr[1]중에서 더 큰 값을 선택하게 됩니다. dp[0]은 2이고 arr[1]은 -3이기 때문에 max(2+(-3), -3) = -1이 됩니다.

 

이 규칙을 점화식으로 나타나면 dp[i] = max(dp[i-1], i번째 요소) 입니다.

 

이 과정을 1로 시작하는 펄스 수열을 곱한 배열과 -1로 시작하는 펄스 수열을 곱한 배열에 각각 실행하여 둘 중에서 최댓값을 찾아 리턴하면 됩니다.

 

풀이

fileprivate func solution(_ sequence:[Int]) -> Int64 {
    let positiveStartArr = sequence.enumerated().map { (index, value) in    // 1, -1, 1, -1,... 순서로 곱함
        return index % 2 == 0 ? value : value * -1
    }
    
    let negativeStartArr = sequence.enumerated().map { (index, value) in    // -1, 1, -1, 1,... 순서로 곱함
        return index % 2 == 0 ? value * -1 : value
    }
    
    let positiveStartArrMax = getMaxSum(targetArr: positiveStartArr)
    let negativeStartArrMax = getMaxSum(targetArr: negativeStartArr)
    
    return Int64(max(positiveStartArrMax, negativeStartArrMax))
}

fileprivate func getMaxSum(targetArr: [Int]) -> Int {
    var dp = Array(repeating: -Int.max, count: targetArr.count) // i번째 인덱스를 끝으로 가지는 서브 배열의 최댓값을 기록
    
    dp[0] = targetArr[0]
    
    for i in 1..<targetArr.count {
        let cur = targetArr[i]
        dp[i] = max(cur, dp[i-1]+cur)
    }
    
    return dp.max()!
}

 

 

마무리

단순히 부분 수열 합의 최댓값을 구하는 문제였다면 더 낮은 레벨에 위치했을 것 같습니다.

하지만 펄스 수열이라는 개념을 합쳐서 약간의 혼란을 주고 있습니다.

사실 펄스 수열은 배열의 경우의 수를 2개로 나누는 장치일 뿐 이 문제의 핵심은 단순히 부분 수열 합의 최댓값을 구하는 것이었습니다.