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

🇱🇻3️⃣, 연속 펄스 부분 수열의 합[161988]

 

🧀 프로세스 

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

🔽 문제풀이

sequence 의 길이가 500,000 까지 가능하다는 제약 조건이 있어서 무지성으로 반복문을 돌리면 시간 초과가 발생할 것이다. 또한  펄스 수열을 곱해야 하니까 1부터 시작하는 경우와 -1부터 시작하는 경우 두가지를 모두 고려해야 한다.

그렇기에 생각한 고안은 전체 배열을 1부터 곱한 배열 한개와 -1부터 곱합 배열 한개에 대한 최대 연속 부분 수열의 합을 구하는 방법을 고안했다. 하나하나 살펴보자.

 

public static long maxSum(int[] arr) {
    long max = 0L;
    long[] dp = new long[arr.length];

    dp[0] = arr[0];
    max = arr[0];

    for(int i=1; i<dp.length; i++) {
        // 이전까지의 최대값 + 현재값 과 현재값을 비교
        dp[i] = Math.max(dp[i-1] + arr1[i], arr1[i]);
        max = Math.max(dp[i], max);
    }          

    return max;
}

 

연속 부분 수열의 최대 합을 구하는 알고리즘을 구현했다. 이전까지의 최대값 + 현재 값, 현재 값을 비교하여 dp 에 저장하고 max 의 값을 갱신한다. 이러한 방식으로 최대 합을 도출했다.

public long solution(int[] sequence) {
    int[] seq1 = new int[sequence.length];
    int[] seq2 = new int[sequence.length];

    for(int i=0; i<sequence.length; i++) {
        if(i%2==0) {
            seq1[i] = sequence[i];
            seq2[i] = sequence[i] * -1;
        } else {
            seq1[i] = sequence[i] * -1;
            seq2[i] = sequence[i];
        }
    }

    return maxSum(seq1, seq2);
}

 

위와 같은 방법을 통해 seq1 은 1부터, seq2 는 -1부터 곱한 펄스 수열을 구현한 후, maxSum 을 통해 한번에 답을 도출했다.

 

✅ 전체코드 

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

public class Solution {
    public static void main(String[] args) {
       int[] sequence = {2,3,-6,1,3,-1,2,4};
       long answer = solution(sequence);
       System.out.println(answer);
    }

    static long solution(int[] sequence) {
        int[] seq1 = new int[sequence.length];
        int[] seq2 = new int[sequence.length];

        for(int i=0; i<sequence.length; i++) {
            if(i%2==0) {
                seq1[i] = sequence[i];
                seq2[i] = sequence[i] * -1;
            } else {
                seq1[i] = sequence[i] * -1;
                seq2[i] = sequence[i];
            }
        }

        return maxSum(seq1, seq2);
    }

    public static long maxSum(int[] arr1, int[] arr2) {
        long max = 0L;
        long[] dp1 = new long[arr1.length];
        long[] dp2 = new long[arr1.length];

        dp1[0] = arr1[0];
        dp2[0] = arr2[0];
        max = Math.max(arr1[0], arr2[0]);

        for(int i=1; i<dp1.length; i++) {
            // 이전까지의 최대값 + 현재값 과 현재값을 비교
            dp1[i] = Math.max(dp1[i-1] + arr1[i], arr1[i]);
            dp2[i] = Math.max(dp2[i-1] + arr2[i], arr2[i]);
            max = Math.max(max, Math.max(dp1[i], dp2[i]));
        }          

        return max;
    }
}

 

원소의 값이 100,000까지 가능하다. 최대의 경우 100,000 X 500,000 = 50,000,000,000 로 int 의 최대 범위를 넘을 수 있으므로 long 을 사용함에 주의하자