프로그래머스 3단계 : 연속 펄스 부분 수열의 합 (Java 자바)

문제 설명
어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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의 원소는 정수입니다.

 

입출력 예

 

풀이

주어진 정수 수열에서 연속된 부분 수열을 선택하고, 해당 부분 수열과 같은 길이의 펄스 수열을 원소끼리 곱하여 얻을 수 있는 연속 펄스 부분 수열 중에서 가장 큰 합을 구하는 문제입니다.

동적 프로그래밍(Dynamic Programming)을 사용하여 문제를 해결합니다. 주요 아이디어는 두 가지 펄스 수열을 따로 계산하고, 그 중에서 가장 큰 값을 선택하는 것입니다.

 

dp1과 dp2 배열: 이 두 배열은 각각 펄스 수열을 1로 시작하는 경우와 -1로 시작하는 경우의 최대 연속 부분 수열 합을 저장합니다.

배열 초기화: dp1[0]과 dp2[0]는 첫 번째 원소로 초기화됩니다. 이 값은 주어진 수열의 첫 번째 원소와 동일합니다.

반복문: 주어진 수열을 순회하면서 dp1과 dp2 배열을 업데이트합니다. 펄스 수열 패턴에 따라서 두 가지 경우를 나누어 계산합니다.

펄스 수열 패턴에 따른 값 업데이트:

홀수 인덱스(i % 2 == 1)일 때: 펄스 수열을 -1로 시작하는 경우. 이 때, 현재 수와 이전까지의 합(dp1[i - 1])을 더해주거나 현재 수를 선택하여 최댓값을 계산합니다.

짝수 인덱스(i % 2 == 0)일 때: 펄스 수열을 1로 시작하는 경우. 이 때, 현재 수와 이전까지의 합(dp2[i - 1])을 더해주거나 현재 수를 선택하여 최댓값을 계산합니다.

배열 정렬: 두 배열을 정렬하여 가장 큰 값을 찾기 위해 마지막 인덱스(size)의 값을 선택합니다.

최종 답 반환: dp1과 dp2 중에서 가장 큰 값을 선택하여 answer에 저장하고 반환합니다.

 

import java.util.*;

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;

        // 두 가지 펄스 수열을 따로 계산하기 위한 배열 선언
        long[] dp1 = new long[sequence.length]; // 1로 시작하는 펄스 수열
        long[] dp2 = new long[sequence.length]; // -1로 시작하는 펄스 수열

        // 초기 값 설정: 주어진 수열의 첫 번째 원소로 초기화
        dp1[0] = sequence[0];
        dp2[0] = sequence[0] * -1;

        // 주어진 수열을 순회하면서 펄스 수열의 합을 계산
        for (int i = 1; i < sequence.length; i++) {
            long num = sequence[i]; // 현재 수열의 원소

            if (i % 2 == 1) {
                // 홀수 인덱스일 때, 펄스 수열은 -1로 시작
                // 이전까지의 합과 현재 수를 비교하여 더 큰 값을 선택
                dp1[i] = Math.max(dp1[i - 1] + num * -1, num * -1);
                dp2[i] = Math.max(dp2[i - 1] + num, num);
            } else {
                // 짝수 인덱스일 때, 펄스 수열은 1로 시작
                // 이전까지의 합과 현재 수를 비교하여 더 큰 값을 선택
                dp1[i] = Math.max(dp1[i - 1] + num, num);
                dp2[i] = Math.max(dp2[i - 1] + num * -1, num * -1);
            }
        }

        int size = sequence.length - 1;

        // 계산된 값들을 정렬하여 가장 큰 값 선택
        Arrays.sort(dp1);
        Arrays.sort(dp2);

        // dp1과 dp2 중에서 가장 큰 값 선택
        answer = Math.max(dp1[size], dp2[size]);

        // 결과 반환
        return answer;
    }
}