[프로그래머스 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으로서 가장 큽니다.

 

 

 

 

 

 

나의 코드

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        int[] purseSeqence1 = new int[sequence.length];
        int[] purseSeqence2 = new int[sequence.length];
        
        for(int i=0; i<sequence.length; i++) {
            if(i % 2 == 0) {
                purseSeqence1[i] = sequence[i];
                purseSeqence2[i] = sequence[i] * (-1);
            } else {
                purseSeqence1[i] = sequence[i] * (-1);
                purseSeqence2[i] = sequence[i];
            }
        }
        
        // purseSeqence1와 purseSeqence2 중에서 최대 연속 부분 수열의 합 구하기 
        // sequence의 최대 길이 500,000 * sequence의 원소가 최대 100,000이므로 부분합이 int형보다 커질 수 있으므로 long형으로 선언해야하는 것에 주의
        long[] dp1 = new long[sequence.length];
        long[] dp2 = new long[sequence.length];
        
        dp1[0] = purseSeqence1[0];
        dp2[0] = purseSeqence2[0];
        answer = Math.max(dp1[0], dp2[0]);
        
        for(int i=1; i<sequence.length; i++) {
            dp1[i] = Math.max(purseSeqence1[i], dp1[i-1] + purseSeqence1[i]);
            dp2[i] = Math.max(purseSeqence2[i], dp2[i-1] + purseSeqence2[i]);
            answer = Math.max(answer, Math.max(dp1[i], dp2[i]));
        }
        
        return answer;
    }
}

 

풀이

1. 특정 부분부터 펄스 수열을 곱하는 것은 결국 두 가지의 경우가 생기므로 주어진 sequence의 처음부터 [1, -1, 1, ...]로 되어있는 펄스 수열과 곱한 purseSequence1과 sequence의 처음부터 [-1, 1, -1, 1, ...]로 되어있는 펄스 수열과 곱한 purseSequence2를 생성한다.
2. 그리고 이렇게 두 가지 purseSequence1과 purseSequence2의 연속 부분 수열 중에서 최대 합을 구하면 된다.
3. 연속 부분 수열의 최대 합을 구하는 방법에는 여러가지 경우가 있지만 동적 계획법를 이용하면 O(n)의 시간복잡도로 구할 수 있다.
4. purseSequence1에서 동적 계획법을 이용하기 위한 dp1 배열과 purseSequence2에서 동적 계획법을 이용하기 위한 dp2 배열을 생성한다. (sequence의 최대 길이 500,000 * sequence의 원소가 최대 100,000이므로 부분합이 int형보다 커질 수 있으므로 long형으로 선언해야하는 것에 주의한다 -> int형으로 선언 시에 테스트 16, 19, 20 실패)
5. dp[0]은 purseSequence[0]의 값과 같으므로 dp1[0]과 dp2[0]을 각각 purseSequence1[0]과 purseSequence2[0]으로 초기화한다.
6. 그리고 인덱스 1부터 sequence의 길이만큼 for문을 돌면서 dp1[i]과 dp2[i]를 각각 업데이트하며 최댓값을 answer에 저장한다.
7. dp[i]의 최댓값은 바로 전의 dp[i]와 현재 purseSequence를 더했을 때와 현재 purseSequence를 비교하여 큰 값을 dp에 저장한다.
8. 현재 purseSequence 값이 dp[i-1] + 현재 purseSequence 값보다 크다면 현재부터 다시 연속으로 더하는 것이 크기 때문에 dp[i]에는 현재 purseSequence 값이 들어간다. 그게 아니라면 dp[i-1] + 현재 purseSequence값이 현재 purseSequence 보다 더 크기 때문에 연속으로 계속 더해주는 것이 더 크다.
9. 물론 현재 purseSequence 값보다 dp[i-1] + 현재 purseSequence 값이 크지만 이 dp의 값이 최대는 아닐 수 있다.
   (예를 들면 dp[3] = 10, purseSequence[4] = -3 의 경우 dp[4] = 7로 dp[3]보다 작아진다)
10. 따라서 dp의 값을 업데이트 하면서 현재 dp의 값과 answer를 비교하며 큰 값을 answer에 저장하며 answer에 최댓값으로 업데이트 하면 된다.