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

DP는 코딩테스트의 정석 같은 문제죠?

바로 풀어보겠습니다!

 

이 문제 저번에도 풀었던 문제로

그 때는 정답을 보았던 것으로 기억하는데,

이 번에는 스스로 풀었습니다 하핫

 

 

---

문제

 

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

프로그래머스

 

 

---

설계

 

알고리즘 설계 [접근 방법] : DP

최대 합을 찾기 위해 어디서 시작하든 상관 없었기에 슬라이딩 윈도우를 생각했지만, 배열의 최대 길이가 500,000이기 때문에 시간 초과가 발생할 것이라 생각했다. 

그래서 DP로 구현했으며, { -1, 1} 그리고 {1, -1} 를 한 번씩 곱해주며, 그 때마다 최대 값을  찾고 비교하는 방식으로 풀었다.

 

DP의 방식은 여태까지 더한 값 or 현재 시작하는 값을 비교하여 더 큰 값을 저장하는 방식으로 풀었다.

 

풀이 과정

1.

매개변수로 받은 펄스 수열에 1, -1를 순차적으로 곱하는 배열 arr1를 생성한다.

 

2.

매개변수로 받은 sequence 배열의 크기만큼 dp 배열을 생성하고, dp[0]은 펄스 수열의 첫 번째 값으로 초기화한다.

 

3.

현재 값 arr[i]와 여태까지 합을 곱한 dp[i-1]+arr[i]의 값을 비교한다.

만약 현재 값 arr[i]가 더 크다면, 지금 현재부터 연속 펄스를 시작해야 하므로 dp[i]의 값은 arr[i]가 된다.

dp[i-1]+arr[i] 값이 더 크다면, 여태까지 더한 값에 현재 값을 더한 값이 더 크다는 뜻이므로 dp[i]는 dp[i-1]+arr[i] 값이 된다.

 

4.

dp배열을 모두 채우면, 반복문을 돌면서 최대 값을 찾는다.

 

5.

{1, -1}를 곱한 펄스 수열의 최대 합을 찾았으므로, 이제 {-1, 1}를 곱한다.

 

6.

아까와 마찬가지로, dp 배열을 생성하고 현재 값과 여태까지의 합을 계속 비교한 뒤 큰 값을 dp배열에 저장한다.

 

7.

현재 dp배열을 탐색하면서 아까 찾은 최대 값과 비교한다.

 

8.

최대 값을 반환한다.

 

---

코드

 

import java.util.*;

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        //펄스 수열
        long[] arr1 = new long[sequence.length];
        for(int i=0; i<arr1.length; i++){
            if(i%2==0) arr1[i] = sequence[i];
            else arr1[i] = sequence[i] * -1;
        }
        
        //dp
        long[] dp = new long[arr1.length];
        dp[0] = arr1[0];
        
        for(int i=1; i<dp.length; i++){
            if(arr1[i]<=dp[i-1]+arr1[i]) dp[i] = dp[i-1]+arr1[i];
            else dp[i] = arr1[i];
        }
        
        //최대값 찾기
        for(int i=0; i<dp.length; i++){
            if(answer<dp[i]) answer = dp[i];
        }
        
        //펄스 수열2
        long[] arr2 = new long[sequence.length];
        for(int i=0; i<arr2.length; i++){
            if(i%2==0) arr2[i] = sequence[i] * -1;
            else arr2[i] = sequence[i];
        }
        
        //dp 2
        dp = new long[arr2.length];
        dp[0] = arr2[0];
        
        for(int i=1; i<dp.length; i++){
            if(arr2[i]<=dp[i-1]+arr2[i]) dp[i] = dp[i-1]+arr2[i];
            else dp[i] = arr2[i];
        }
        
        //최대값 찾기2
        for(int i=0; i<dp.length; i++){
            if(answer<dp[i]) answer = dp[i];
        }

        return answer;
    }
}

 

 

(❁´◡`❁)

끝!