프로그래머스 연속 펄스 부분 수열의 합 자바 풀이

문제 링크

문제 풀이 시간 : 1시간

문제 요약

정수 수열 sequence가 주어짐
연속된 일부 구간(부분 수열)을 선택하고 같은 길이의 펄스 수열을 각 원소에 곱함
펄스 수열은 두 가지 형태 중 하나
곱셈 결과로 만들어진 연속 펄스 부분 수열의 합 중 가장 큰 값을 구하기

문제 풀이

처음 이 문제를 보고 부분 합을 구해야겠다는 생각을 하고 일단 1로 시작하는 펄스 수열과 -1로 시작하는 펄스 수열을 각각 곱해서 순차합을 구해보았다.

예시와 같이 [2, 3, -6, 1, 3, -1, 2, 4] 라는 수열이 있을 때, 1과 -1로 시작하는 펄스 수열을 곱하면 아래와 같다.

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

그리고 각 수열의 순차 합은 아래와 같다.

1로 시작하는 펄스 수열을 곱한 경우 : [2, -1, -7, -8, -5, -4, -2, -6]
1로 시작하는 펄스 수열을 곱한 경우 : [-2, 1, 7, 8, 5, 4, 2, 6]

이 두가지 수열을 자세히 살펴보면 그냥 부호가 반대이고 동일한 수열인 것을 알 수 있다!

그래서 우리는 한가지 경우에 대해서만 계산하고 절댓값을 통해 최대 부분 수열의 합을 구할 수 있다.

그러면 이제 최대 부분 수열의 합을 구하는 것이 문제인데

이건 아주 쉽다.

우리는 이미 연속된 부분 수열의 합을 구해두었기 때문에 그런 부분 수열의 합 중에서 가장 큰 것과 작은 것을 빼주면 되는 것이다.

위의 1로 시작하는 펄스 수열에서 가장 큰 값은 2이고, 가장 작은 값은 -8 이므로 두가지 값을 빼주면 10이라는 최댓값이 나오게 된다.

초기 코드

java

import java.util.*;

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        int len = sequence.length;
        long[] sum = new long[len+1];
        
        sum[0] = sequence[0];
        sum[len] = 0;
        for(int i=1;i<len;i++){
            if(i%2==0)
                sum[i] = sum[i-1]+sequence[i];
            else
                sum[i] = sum[i-1]-sequence[i];
        }
        
        Arrays.sort(sum);
        answer = sum[len] - sum[0];
        
        return answer;
    }
}

처음엔 위와 같이 코드를 작성했다.

물론 이 코드도 동작하고 통과하는 코드이지만 생각해보니 이렇게 sum 배열을 계산하고, 정렬을 하는 불필요한 동작이 필요가 없었다!

최종 코드

java

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        int len = sequence.length;
        
        long max = 0L;
        long min = 0L;
        long sum = 0L;
        for(int i=0;i<len;i++){
            if(i%2==0)
                sum += sequence[i];
            else
                sum -= sequence[i];
            
            max = Math.max(max, sum);
            min = Math.min(min, sum);
        }
        
        return max - min;
    }
}

또 다른 풀이

이 문제는 당연히 다른 방식으로도 풀 수 있다.

부분 수열의 합을 구하는 방법에는 Kadane 알고리즘이 있다.

Kadane 알고리즘에 대한 설명은 블로그에 정리해두었다.

Kadane 알고리즘 코드

java

class Solution {
    public long solution(int[] sequence) {
        long answer = 0L;
        long dp0 = 0L; // 1로 시작하는 펄스수열을 곱한 수열의 최대 부분합
        long dp1 = 0L; // -1로 시작하는 펄스수열을 곱한 수열의 최대 부분합

        for (int i = 0; i < sequence.length; i++) {
            if ((i & 1) == 0) { // 짝수 인덱스
                dp0 = Math.max(0L, dp0) + sequence[i];
                dp1 = Math.max(0L, dp1) - sequence[i];
            } else {            // 홀수 인덱스
                dp0 = Math.max(0L, dp0) - sequence[i];
                dp1 = Math.max(0L, dp1) + sequence[i];
            }
            answer = Math.max(answer, Math.max(dp0, dp1));
        }
        return answer;
    }
}

연속 펄스 부분 수열의 합

문제 풀이 시간 : 1시간

문제 요약

문제 풀이

초기 코드

최종 코드

또 다른 풀이

Kadane 알고리즘 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기