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

 

수열의 연속된 부분에 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 같은 펄스 수열을 곱했을 때 만들 수 있는 연속 펄스 부분 수열의 합 중 최댓값을 구하는 문제다. 수열의 길이는 최대 500,000, 각 원소는 최대 ±100,000까지 가능하다는 제약이 있었다.

✏️아이디어

수열 전체에 펄스 수열을 곱해보자.
펄스는 [1,-1,1,-1…]로 시작하는 경우와 [-1,1,-1,1…]로 시작하는 경우 두 가지가 있다. 각각 곱한 배열을 만들어보면,
2 3 -6 1 3 -1 2 4 (원본)
2 -3 -6 -1 3 1 2 -4 (1,-1,1,-1… 곱 even)
-2 3 6 1 -3 -1 -2 4 (-1,1,-1,1… 곱 odd)

그럼 이 두 배열 각각에서 연속 구간의 합 중 최댓값을 구하면 되는 거 아닐까?
- 두 배열의 누적합을 구해보자
2 -1 -7 -8 -5 -4 -2 -6 (even 누적합)
-2 1 7 8 5 4 2 6 (odd 누적합)

odd 누적합 배열에서 최댓값(8, 4번째)을 찾았다
0번째부터 그 인덱스까지 누적합을 하나씩 빼보면서 최댓값이 갱신되는지 확인해보자

8 - (-2) = 10
8 - 1 = 7
8 - 7 = 1
8 - 0 = 8
-> 이 중 최댓값인 10이 나온다.
결국 누적합에서 (현재까지의 누적합) - (그 이전까지의 최솟값)을 구하면 연속 구간의 최대합을 구할 수 있다는 뜻이다
odd, even 두 방향에 대해 각각 구한 값 중 더 큰 값을 반환하면 될 것 같다

 

💡풀이

import java.util.*;
import java.util.stream.*;

class Solution {
    public long solution(int[] sequence) {

        // 각각 1, -1 펄스로 시작하는 구간합 배열 만들기
        long[] oddPrefixSum = new long[sequence.length + 1];
        long[] evenPrefixSum = new long[sequence.length + 1];

        for(int i=1; i< sequence.length + 1; i++){  
            int oddSequence = sequence[i-1] * (i%2==0 ? 1 : -1);
            int evenSequence = sequence[i-1] * (i%2==0 ? -1 : 1);

            oddPrefixSum[i] = oddPrefixSum[i-1] + oddSequence;
            evenPrefixSum[i] = evenPrefixSum[i-1] + evenSequence;           
        }

        return Math.max( findMaxSum(oddPrefixSum), findMaxSum(evenPrefixSum) );

    }

    public long findMaxSum(long[] prefixSum){

        long minPrefix = prefixSum[0];
        long max = Long.MIN_VALUE;

        for(int i=1; i<prefixSum.length; i++){

            long sum = prefixSum[i] - minPrefix;
            max = Math.max(max, sum);
            minPrefix = Math.min(minPrefix, prefixSum[i]);

        }

        return max;
    }

}

누적합 배열을 odd, even 두 방향으로 각각 만들어두고, findMaxSum에서 지금까지의 최솟값(minPrefix)을 빼주는 방식으로 구간의 최대합을 구했다. minPrefix는 먼저 현재 값으로 합을 구한 뒤에 갱신해야, 자기 자신보다 이전 위치의 최솟값만 반영된다.

---

❌ 처음엔 왜 틀렸을까

사실 처음에 제출했던 코드는 로직은 거의 동일한데 결과가 틀렸다.

import java.util.*;
import java.util.stream.*;

class Solution {
    public long solution(int[] sequence) {
        // 1, -1로 시작하는 펄스곱 배열만들기
        int length = sequence.length;
        int[] oddSequence = new int[length]; // 홀수가 음수
        int[] evenSequence = new int[length]; // 짝수가 음수

        for(int i=0; i<length; i++){  

            if(i%2==0){
                oddSequence[i] = sequence[i];
                evenSequence[i] = sequence[i] * -1;
            } else {
                oddSequence[i] = sequence[i] * -1;
                evenSequence[i] = sequence[i];
            }            
        }

        // 1, -1로 시작 구간합 배열 만들기
        int[] oddPrefixSum = new int[length + 1];
        int[] evenPrefixSum = new int[length + 1];

        for(int i=0; i<length; i++){
            oddPrefixSum[i+1] = oddPrefixSum[i] + oddSequence[i];
            evenPrefixSum[i+1] = evenPrefixSum[i] + evenSequence[i];
        }

        int oMax = findMaxSum(oddPrefixSum);
        int eMax = findMaxSum(evenPrefixSum);

        return Math.max(oMax, eMax);

    }

    public int findMaxSum(int[] arr){

        int minPrefix = 0;
        int max = arr[1];

        for(int i=1; i<arr.length;i++){
            minPrefix = Math.min(arr[i], minPrefix);

            int sum =  arr[i] - minPrefix;
            if(max < sum) max = sum;
        }

        return max;
    }

}

 

처음엔 로직이 똑같으니 타입만 다른 거 아닌가 싶었는데, 원인은 oddPrefixSum, evenPrefixSum을 int[]로 선언한 부분이었다.

 

수열의 길이가 최대 500,000이고 원소가 최대 ±100,000이니, 누적합의 절댓값은 최대 500,000 * 100,000 = 500억(5 * 10^10)까지 커질 수 있다.

int의 최댓값은 약 21억(2,147,483,647) 수준이라, 값이 큰 테스트케이스에서는 누적합을 더하는 과정에서 이미 오버플로우가 발생해버린다.

solution의 리턴 타입이 long이라고 해도 소용없었다.

오버플로우는 리턴하는 시점이 아니라, oddPrefixSum[i+1] = oddPrefixSum[i] + oddSequence[i]; 처럼

int끼리 더하는 연산 자체에서 이미 발생하기 때문이다.

그래서 결국 누적합을 담는 배열을 long[]으로 바꾸고 나서야 큰 테스트케이스에서도 정답이 나왔다.

---

📖새로 배운 부분

1. 리턴 타입이 long이어도, 계산에 쓰는 변수/배열이 int면 오버플로우를 막을 수 없다.
   오버플로우는 값을 더하거나 곱하는 연산이 실행되는 그 순간에 발생한다. 최종 리턴 타입만 크게 잡아둔다고 해결되는 게 아니라, 연산에 실제로 관여하는 모든 변수의 타입을 확인해야 한다는 걸 알게 됐다.
2. 최댓값이 항상 0 이상이 되는 문제도 있다.
   펄스는 부호를 자유롭게 뒤집을 수 있기 때문에, 원소 하나짜리 부분 수열만 보더라도 항상 절댓값만큼의 양수를 만들 수 있다. 그래서 이 문제는 어떤 수열이 주어져도 답이 음수가 될 수 없다는 특징이 있었다.
3. 최댓값과 최솟값을 함께 갱신할 땐 갱신 순서를 신경 써야 한다.
   minPrefix를 먼저 현재 값까지 포함해서 갱신해버리면, 자기 자신을 빼서 구간 길이가 0인 경우까지 후보에 들어가 버린다. 이번 문제에서는 답에 영향을 주지 않았지만, 다른 문제였다면 오답으로 이어질 수 있었던 부분이라 갱신 순서를 항상 의식해서 짜는 습관을 들여야겠다고 생각했다.