[프로그래머스 Level 3] 연속 펄스 부분 수열의 합 (Java)

🚀링크

https://school.programmers.co.kr/learn/courses/30/lessons/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 함수를 완성해주세요.

제한 사항

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

입출력 예

sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

입출력 예 설명

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

🌏문제풀이

1. 우선, 2개의 새로운 배열, [-1, 1, -1, ..] 형태의 펄스 수열을 곱한 연속 펄스 수열 sequence1과 [1, -1, 1, ...] 형태의 펄스 수열을 곱한 sequence2를 만들었다.
2. 문제가 부분수열 관련 이라는 점에서 투포인터 알고리즘으로 접근하였다.
3. total 변수값이 0보다 큰 경우에만 while 문을 돌려서 total 변수에 누적합을 저장하였고, answer의 값과 비교하여 최댓값을 지속적으로 업데이트 했습니다.

💻코드

class Solution {
    public long solution(int[] sequence) {
        int N = sequence.length;
        long answer = 0;
        
        // sequence에 [-1, 1, -1, ...] 형태의 펄스 수열을 곱한 연속 펄스 수열
        int[] sequence1 = new int[N];
        for(int i = 0; i < N; i++) {
            if(i % 2 == 0) {
                sequence1[i] = -sequence[i];
            } else {
                sequence1[i] = sequence[i];
            }
        }
        
        // sequence에 [1, -1, 1, ...] 형태의 펄스 수열을 곱한 연속 펄스 수열
        int[] sequence2 = new int[N];
        for(int i = 0; i < N; i++) {
            if(i % 2 == 1) {
                sequence2[i] = -sequence[i];
            } else {
                sequence2[i] = sequence[i];
            }
        }
        
        long total = 0;
        for(int L = 0, R = 0; L < N; L++) {
            while(total >= 0 && R < N) {
                total += sequence1[R];
                answer = Math.max(total, answer);
                R++;
            }
            total -= sequence1[L];
        }
        
        total = 0;
        for(int L = 0, R = 0; L < N; L++) {
            while(total >= 0 && R < N) {
                total += sequence2[R];
                answer = Math.max(total, answer);
                R++;
            }
            total -= sequence2[L];
        }
        
        return answer;
    }
}