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

Level3 - 연속 펄스 부분 수열의 합

프로그래머스

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

제한 조건

1 ≤ sequence의 길이 ≤ 500,000 100,000 ≤ sequence의 원소 ≤ 100,000 sequence의 원소는 정수입니다.

입출력 예
sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10
입출력 예#1 주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

​

풀이 접근 과정

처음엔 이중 for을 사용하여 모든 부분합을 구하였다. 이 방식은 제한 조건의 범위가 넓어 시간 초과가 난다.

그래서 수정했던 방법이 두개의 배열을 만들어서 '양수만 연속되는 부분 배열을 더하면 되지 않을까?' 였는데, 이 방식은 약 20점의 점수가 나왔다.

그 이유는 [양수,양수,양수, 음수,양수] 일 때 양수 3개만 더하는 것보다 음수를 포함하여 뒤에 양수까지 더했을 때의 값이 더 높은 경우가 있기 때문이다.

 

나의 목표는 반복문을 단 한 번만 사용하여 코드를 짜는 것이었다. (dp는 생각하는게 귀찮아서 배제함...ㅎㅎ)

그러다가 누적합을 떠올렸다.

[1,-1,1...] 과 [-1,1,-1...] 을 곱한 배열의 누적합을 각각 구한 후 max 값과 min 값을 구하면 그 사이의 부분합이 나온다.

 

예를 들어 배열 [2, 3, -6, 1, 3, -1, 2, 4]의 누적합을 구하면 [2, 5, -1, 0, 3, 2, 4, 6]이 된다.

이때 누적합은 최댓값은 6이고 최솟값은 -1이다.

여기서 부분합의 최댓값은 6-(-1) = 7이라는 결과가 도출된다. 

 

그래서 max-min 값을구해서 리턴했더니 70점이 나왔다.

놓친 부분이 있다. 숫자가 단 한개인 배열이어도 그것도 부분배열이다.

그래서 max와 max-min도 비교하여 리턴하였더니 통과하였다.         

 

나의 최종 풀이

1. 1,-1,1 혹은 -1,1,-1 의 순서대로 곱한 배열의 누적합을 각각 pulseSum1과 pulseSum2로 만든다.
2. pulseSum1의 max과 pulseSum2의 max 중에서 큰 값을 리턴한다.
   • pulseSum1의 max-min의 값이 max 값보다 크면 max는 max-min이 된다.
   • pulseSum2의 max-min의 값이 max 값보다 크면 max는 max-min이 된다.

class Solution {
    fun solution(sequence: IntArray): Long {
        val pulseSum1 = LongArray(sequence.size) { 0 }
        val pulseSum2 = LongArray(sequence.size) { 0 }

        var min1 = Long.MAX_VALUE
        var max1 = Long.MAX_VALUE * -1
        var min2 = Long.MAX_VALUE
        var max2 = Long.MAX_VALUE * -1

        sequence.forEachIndexed { index, i ->
            if (index == 0) {
                pulseSum1[index] = (i * -1).toLong()
                pulseSum2[index] = i.toLong()
            } else if (index % 2 != 0) {
                pulseSum1[index] = pulseSum1[index-1] + i
                pulseSum2[index] = pulseSum2[index-1] + i * -1
            } else {
                pulseSum1[index] = pulseSum1[index-1] + i * -1
                pulseSum2[index] = pulseSum2[index-1] + i
            }

            if (pulseSum1[index] < min1) min1 = pulseSum1[index]
            if (pulseSum1[index] > max1) max1 = pulseSum1[index]
            if (pulseSum2[index] < min2) min2 = pulseSum2[index]
            if (pulseSum2[index] > max2) max2 = pulseSum2[index]
        }

        if (max1 - min1 > max1) max1 -= min1
        if (max2 - min2 > max2) max2 -= min2

        return if (max1 >= max2) max1 else max2
    }
}