연속 펄스 부분 수열의 합(프로그래머스- 연습문제)

문제

코드

class Solution {
    public long solution(int[] sequence) {
        long answer = Math.max(sequence[0],-sequence[0]);
        int[] arr1=new int[sequence.length];
        int[] arr2=new int[sequence.length];
        long[] dp1=new long[sequence.length];
        long[] dp2=new long[sequence.length];
        
        int pulse=1;
        for(int i=0;i<sequence.length;i++){
            arr1[i]=sequence[i]*pulse;
            arr2[i]=sequence[i]*(-pulse);
            pulse*=-1;
        }
        
        dp1[0]=arr1[0];
        dp2[0]=arr2[0];

        for(int i=1;i<sequence.length;i++){
            if(arr1[i]+dp1[i-1]>arr1[i]) dp1[i]=arr1[i]+dp1[i-1];
            else dp1[i]=arr1[i];
            
            if(arr2[i]+dp2[i-1]>arr2[i]) dp2[i]=arr2[i]+dp2[i-1];
            else dp2[i]=arr2[i];
            
            answer=Math.max(answer,dp1[i]);
            answer=Math.max(answer,dp2[i]);
        }
        return answer;
    }
}

풀이

(1) 1로 시작하는 전체 펄스 수열, -1로 시작하는 전체 펄스 수열을 저장할 배열을 2개 생성한다(arr1, arr2).
(2) arr1, arr2 의 각 인덱스별 최댓값을 저장할 배열을 2개 생성한다.(dp1, dp2)
(3) arr1에는 sequence배열에서 0번째 요소부터 1, -1, 1, -1... 을 곱한 값을 넣어주고, arr2에는 -1, 1, -1, 1... 을 곱한값을 넣어준다.
(4) arr1, arr2를 돌면서 각 요소마다 만들수 잇는 최댓값을 갱신하여 준다.

• arr[i]+dp[i-1] > arr[i]이면 dp[i]=arr[i]+dp[i-1] 이 되고, 그렇지 않으면 dp[i]=arr[i]가 된다.
• 위를 배열 끝까지 돌면서, answer을 갱신하여 준다.

결과

dp문제라는 것을 생각할수만 있다면 크게 어렵지 않은 문제이다.
이 문제를 처음 봤을땐 큐를 사용해야 할 것 같기도 하고, 그리디 인 것 같기도 하고 헷갈렸지만, 좀 더 신중하게 천천히 생각해봤더니 dp로 풀 수 있을 것 같다는 생각이 들었다.
1로 시작하는 펄스 전체 수열, -1로 시작하는 펄스 전체 수열을 만들어야 겠다는 생각을 떠올린다면, dp로 쉽게 풀 수 있었다.
레벨3 문제치고 막 어렵진 않은 문제였다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges