[프로그래머스/JavaScript] Lv.3 연속 펄스 부분 수열의 합

 

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

프로그래머스

 

 

---

1. 문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 함수를 완성해주세요.

 

제한 사항

 

 

---

2. 입출력 예

입출력 예

 

 

 

---

3. 문제 풀이

다이나믹 프로그래밍(Dynamic Programming) 자료구조 방법을 사용하여 한번 구한 값은 저장해 다시 계산하지 않도록 한다.

DP(Dynamic Programming)이란?
하나의 문제를 단 한 번만 계산하는 자료구조 방법이다.
주로 "작은 문제가 반복이 일어나는 경우" , "같은 문제는 구할 때마다 정답이 같은 경우" 사용된다. 
ex) 피보나치수열( Fn = F(n-1) + F(n-2) ), 배열 합, 배열의 최댓값  등

 

function solution(sequence) {
    var answer = 0;
    // 1) 1, -1로 시작하는 펄스에 따른 값을 저장(Memoization)한다.
    const pSeq = [];  // 1부터 시작
    const mSeq = [];  // -1부터 시작

    // 2) DP 자료구조 방법을 사용하여 최댓값을 구해 저장한다.
    for(let i=0; i<sequence.length; i++) {
        
        // 3) 최초, 짝수, 홀수일 경우에 발생하는 펄스를 곱한다.
        if(i === 0) {
        
            // 4) 최초 값은 펄스 값만 곱하고 저장한다.
            pSeq.push(sequence[i]);
            mSeq.push(-sequence[i]);
        } else if(i%2 === 0) {  
        
            // 5) 최댓값만 구하면 되기 때문에 기존 저장된 값에 더한 값과
            //    처음부터 시작하는 값 중 최댓값을 찾아 저장한다.
            pSeq.push(Math.max(pSeq[i-1] + sequence[i], sequence[i]));
            mSeq.push(Math.max(mSeq[i-1] - sequence[i], -sequence[i]));
        } else {
        
            // 6) 5번과 마찬가지로 최대값을 찾아 저장한다.
            pSeq.push(Math.max(pSeq[i-1] - sequence[i], -sequence[i]));
            mSeq.push(Math.max(mSeq[i-1] + sequence[i], sequence[i]));
        }
        
        // 7) 가장 큰 값을 찾기 때문에 answer에 현재 구한 값의 최댓값을 저장한다.
        answer = Math.max(answer, pSeq[i], mSeq[i]);
    }
 
    return answer;
}