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

문제 설명 

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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의 원소는 정수입니다.

 

---

문제 풀이

이차원 배열로 풀 수 있는 전형적인 dp 문제였던 것 같다. 백준에서 dp 문제 풀이 연습을 하면서 많이 봐왔던 패턴이라 문제 설명을 보면서 'dp로 풀면 되지 않을까' 생각을 했었는데 아니나 다를까 문제의 이름이 '연속 펄스 부분 수열의 합'이었다. 부분 수열의 합, 부분 수열의 최대값, 부분 수열의 최소값 같은 네이밍이 나오면 보통 dp 문제던데, 이 경우도 이런 추론이 들어맞았던 것 같다.

 

문제 풀이의 논리적인 흐름은 다음과 같았다.

 

1. 문제를 4가지의 경우로 나누어 생각해보자.
   1. -1로 시작하는 펄스가 기존의 연속 부분 수열을 이어가는 경우
   2. 1로 시작하는 펄스가 기존의 연속 부분 수열을 이어가는 경우
   3. -1로 시작하는 펄스가 새로 부분 수열을 시작하는 경우
   4. 1로 시작하는 펄스가 새로 부분 수열을 시작하는 경우
2. 각각의 경우를 각각 계산한 후 dp 배열에 담는다.
3. 이후 sequence의 인덱스를 증가시켜가며 1번을 반복하되, 이전 계산값의 최대값을 고려해 최대값을 기록하자.
4. 3번의 경우 고려해야 할 부분은 값이 1로 시작되는 경우는 이전의 -1로 끝난 경우로 연산을 해야 하고, -1로 시작되는 경우는 이전의 1로 끝난 경우로 연산을 해야 한다는 점이다.
5. 연산이 완료된 dp 2차원 배열을 순회하며 값의 최대값을 찾아 정답으로 제출한다.

 

아래의 입력 예와 위의 논리 회로를 통해 만들어낸 2차원 배열을 살펴보자.

 

입력

2

3

-6

1

3

 

이차원 배열

index	(1)	(2)	(3)	(4)
0	-2	2	-2	2
1	-1	1	-3	3
2	9	-7	6	-6
3	-7	10	-1	1
4	7	2	-3	3

* (1) (2) (3) (4) : 논리 흐름 1번의 1번, 2번, 3번, 4번

 

문제 풀이 코드

class Solution {
    
    long[][] dp;
    
    public long solution(int[] sequence) {
        dp = new long[sequence.length][4];

        dp[0][0] = sequence[0] * -1;
        dp[0][1] = sequence[0];
        dp[0][2] = sequence[0] * -1;
        dp[0][3] = sequence[0];

        for (int i = 1; i < sequence.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][3]) + sequence[i] * -1;
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][2]) + sequence[i];
            dp[i][2] = sequence[i] * -1;
            dp[i][3] = sequence[i];
        }

        long result = 0;
        for (int i = 0; i < sequence.length; i++) {
            result = Math.max(result,
                    Math.max(dp[i][0],
                            Math.max(dp[i][1],
                                    Math.max(dp[i][2], dp[i][3]))));
        }

        return result;
    }
}