[프로그래머스] 연속 펄스 부분 수열

문제

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

 

---

접근

처음에 이문제를 봤을때 느꼈던 거는, O(N^2)으로 풀면안되겠다고 느꼈습니다.

길이가 500000이기 때문에.

당연히 누적합을 구해서 모든 i부터 j까지의 구간합을 구해서 max값을 찾는 방식은 시간초과가 날 것이라 생각하고 다른 방법을 고민했습니다.(i,j는 0부터 sequence의 길이)

 

그래서 계속 고민을하다가 그냥 코드를 짜보기로했습니다.

누적합을 일단 만들어보니 해답이 보였는데,

누적합 최대값에서 누적합 최소 값을 빼면 정답이 나오는걸 찾을 수 있었습니다.(순서대로 탐색해야함)

따라서 나는 N개의 길이만큼 [1,-1,1,…..], [-1,1,-1,…]의 두가지 펄스 배열을 만든 후, 기존의 배열에 곱해줘서 새로운 배열을 2개만들어 준 다음 누적합 2개를 만들어서 누적합 차를 이용해 문제를 해결했습니다.

이렇게하면 O(N)만에 정답을 도출해 낼 수 있습니다.

 

근데 다른 사람의 풀이를 보고나니, 누적합을 만들어가면서 음수일때는 0으로 초기화해주고, 양수일 때는 더해주면서 max값을 찾는 방식도 있었습니다. 이 방법이 훨씬 간단하다는 생각이 들었습니다.

뭔가 원리는 내 풀이와 비슷한데, 훨씬 간단히 구현할 수 있는 것 같습니다.

여지껏 누적합의 결과물을 이용하는 것만 생각했었는데, 누적합 만들어가면서 로직을 합치는 테크닉을 배운 것 같습니다.

---

코드

function solution(sequence) {
    var answer = 0;
    const sumArr1 = [];
    const sumArr2 = [];
    let arr1 = [];
    let arr2 = [];
    arr1 = [...sequence];
    arr2 = [...sequence];
    for(let i=0; i<sequence.length; i+=2){
        arr1[i] *= -1;
        //그냥 하나의 값이 정답이 될 수 있으므로
        answer = Math.max(answer,arr1[i]);
    }
    for(let i=1; i<sequence.length; i+=2){
        arr2[i] *= -1;
        //그냥 하나의 값이 정답이 될 수 있으므로
        answer = Math.max(answer,arr2[i]);
    }
    sumArr1[0] = arr1[0];
    sumArr2[0] = arr2[0];
    let max1 = sumArr1[0];
    let max2 = sumArr2[0];
    let min1 = sumArr1[0];
    let min2 = sumArr2[0];
    for(let i=1; i<sequence.length; i++){
        sumArr1[i] = sumArr1[i-1] + arr1[i];
        sumArr2[i] = sumArr2[i-1] + arr2[i];
        //그냥 하나의 값이 정답이 될 수 있으므로
        answer = Math.max(answer,sumArr1[i],sumArr2[i]);
        if(sumArr1[i] > max1){
            max1 = sumArr1[i];
            answer = Math.max(answer,max1 - min1);
        }
        if(sumArr1[i] < min1){
            min1 = sumArr1[i];
            answer = Math.max(answer, max1 - min1);
        }
        if(sumArr2[i] > max2){
            max2 = sumArr2[i];
            answer = Math.max(answer,max2 - min2);
        }
        if(sumArr2[i] < min2){
            min2 = sumArr2[i];
            answer = Math.max(answer, max2 - min2);
        }
    }
    return answer;
}

---

주의

주의 해야할 점은,

1. 값 하나가 정답이 될 수 도 있습니다. ex) -10, -10, -10, -10, 300, -50,-50 이런경우 300이 정답.
2. 누적합에서도 값 하나가 정답이 될 수 있습니다. ex 누적합) 100, 200, 300, 400, 500 의 경우 500이 정답이다. 500-100이 정답이 아님.