[JavaScript] Programmers 연속 펄스 부분 수열의 합 (JS)

연속 펄스 부분 수열의 합

📚 문제 설명

sequence 수열이 주어진다. 해당 수열에 각각의 원소에 펄스 수열을 곱하여 펄스 부분 수열을 만들려고 한다.
여기서펄스 수열이란 1 또는 -1 로 시작되어 [1, -1, 1] 과 같이 1과 -1이 교차로 반복되는 수열을 의미한다.
sequence를 이용하여 펄스 부분 수열을 만들었을 때, 펄스 부분 수열의 합이 최대일 때는 몇인가.

👨🏻‍💻 풀이 과정

이 문제를 풀며 첫번째 풀이는 시간초과가 나서 실패하게 되었다.
우선 실패한 풀이부터 설명하려 한다.

💡첫번째 풀이 (완전 탐색) (fail)

모든 연속 부분 수열을 찾아서 CalulateMax 함수를 통해 최댓값을 찾는다.

전체 풀이

    function solution(sequence) {
      	// 최댓값 찾는 함수.
        const CalculateMax = (NumArr) => {
          	// 시작이 +1 로 시작하는 펄스 수열일 때.
            let StartPlus = 0;
          	// 시작이 -1 로 시작하는 펄스 수열일 때.
            let StartMinus = 0;
            let max = 0;
			// 계산 진행.
            for (let i = 0; i < NumArr.length; i++) {
                if (i % 2 === 0) {
                    StartPlus += NumArr[i];
                    StartMinus -= NumArr[i];
                } else {
                    StartPlus -= NumArr[i];
                    StartMinus += NumArr[i];
                }
                let Compare = StartPlus > StartMinus ? StartPlus : StartMinus;
                max = max < Compare ? Compare : max;
            }
            return max;
        };
        let answer = 0;

        const main = () => {
          	// 모든 연속 부분 수열
            for (let i = 0; i < sequence.length; i++) {
                for (let j = i; j < sequence.length; j++) {
                  	// slice를 이용해 연속 부분 수열을 찾음.
                    let max = CalculateMax(sequence.slice(i, j + 1));
                    if (answer < max) {
                        answer = max;
                    }
                }
            }
        };
        main();
        return answer;
    }

💡두번째 풀이 (DP)

첫번째 풀이가 시간초과가 나고 나서 새로운 방법을 알아 보았고,
다이나믹 프로그래밍(DP) 를 이용해서 부분 수열의 최댓값을 찾는 방법을 찾았다.

원리는 생각보다 간단하다.
우리가 알고 싶은 것은 결국 원소합의 최댓값이다.
따라서 1과 -1로 시작하는 2개의 DP 배열을 만든 후, sequence 배열을 하나씩 확인하며 해당 부분까지의 최댓값을 DP배열에 넣어주는 것이다.

예를 들어
sequence = [5, 2, 3] 배열이 주어졌을 때, 2개의 배열 DP1 = [5]와 DP2 = [-5] 가 생긴다. (펄스 수열 1로 시작, -1로 시작 2개)
이제 다음 숫자 2를 확인하는데 Math.max(5 - 2, 2)와 Math.max(-5 + 2, 2) 를 DP[1] 에 넣어준다.
그럼 DP 배열은 각각 [5, 2], [-5, 2] 이렇게 된다.

DP 전체 코드

    function solution(sequence) {

        const CalculateMax = (NumArr) => {
            let StartPlus = [];
            let StartMinus = [];
            let max = 0;

            for (let i = 0; i < NumArr.length; i++) {
              	// 0일 때는 초기값을 설정.
                if (i === 0) {
                    StartPlus.push(sequence[i]);
                    StartMinus.push(-sequence[i]);
                  // 현재 수열까지 최댓값 기록.
                } else if (i % 2 === 0) {
                    StartPlus.push(Math.max(StartPlus[i - 1] + sequence[i], sequence[i]));
                    StartMinus.push(Math.max(StartMinus[i - 1] - sequence[i], -sequence[i]));
                } else {
                    StartPlus.push(Math.max(StartPlus[i - 1] - sequence[i], -sequence[i]));
                    StartMinus.push(Math.max(StartMinus[i - 1] + sequence[i], sequence[i]));
                }
              	// 최댓값 갱신.
                let Compare = StartPlus[i] > StartMinus[i] ? StartPlus[i] : StartMinus[i];
                max = max < Compare ? Compare : max;
            }
            return max;
        };

        return CalculateMax(sequence);
    }

🧐 후기

DP를 이용해 부분 수열의 합을 구하는 방법을 알게 해준 문제이다.
바로 이를 활용해서 다른 문제를 풀어보려고 했는데 부분집합의 합 다이나믹 프로그래밍 문제는 백준에서 모두 다이아 이상이었다.
우선 DP문제를 좀 풀어야겠다.