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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/161988#

문제 풀이

• 구간합, 투포인터 알고리즘을 이용하여 풀이하였다.
• 우선 brute force 사용시 50만 * 50만 정도 복잡도로 시간초과가 발생한다.
• 다음 두 단계로 나누어 풀이한다.

  1. 구간합을 구하되 +로 시작하는 펄스배열 적용 버전, -로 시작하는 펄스배열 적용 버전
     두 가지 구간합을 구해준다. (모든 케이스 커버, 특정 구간의 합을 O(1)복잡도로 구하기 위함)
  2. 각 구간합에 대해서 투포인터 알고리즘을 적용하되 다음 로직을 적용한다.
     - 현재 (lo, hi] 구간합이 양수이면 결과 비교 후 hi만 증가
     - 현재 (lo, hi] 구간합이 음수이면 lo = hi, hi++ (음수인 구간은 필요없음)

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public long solution(int[] sequence) {
        long[] preSumPlus = new long[sequence.length + 1];  //+부터 시작하는
        long[] preSumMinus = new long[sequence.length + 1]; //-부터 시작하는

        //1. +시작 버전, -시작 버전 구간합 구하기
        long pm = 1;
        long plusSum = 0;
        long minusSum = 0;
        for (int i = 0; i < sequence.length; i++) {
            plusSum += sequence[i] * pm;
            preSumPlus[i + 1] = plusSum;
            pm *= -1;
            minusSum += sequence[i] * pm;
            preSumMinus[i + 1] = minusSum;
        }

        //2. 투 포인터 알고리즘
        long result = Long.MIN_VALUE;
        result = getResult(sequence, preSumPlus, result);
        result = getResult(sequence, preSumMinus, result);
        return result;
    }

    public long getResult(int[] sequence, long[] preSum, long result) {
        int lo = 0;
        int hi = 1;
        while(hi <= sequence.length) {
            long sum = preSum[hi] - preSum[lo];
            //구간합이 양수이면 결과 갱신 후 hi 증가
            if (sum >= 0) {
                result = Math.max(result, sum);
                hi++;
            }
            //구간합이 음수이면 다음 lo, hi를 다음 인덱스로 초기화
            else {
                lo = hi;
                hi++;
            }
        }
        return result;
    }
}