[프로그래머스LV3] 연속 펄스 부분 수열의 합 (C++)

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

프로그래머스

 

O(N^2)으로 풀어내면 손쉽게 풀 수 있지만 그렇게 하면 N = 50만이기 때문에 시간초과가 나기 때문에 당연히 시간초과가 난다. 

 

먼저 주목한 부분은 "정해진 범위에 일정한 값을 더한다." 는 것을 주목했다. 그리고 그 정해진 범위의 합을 구해야하는 문제이다.

 

그래서 누적합을 시도해보았다. 

 

예제인

[2, 3, -6, 1, 3, -1, 2, 4] 이라고 해보자

 

	2	3	-6	1	3	-1	2	4
1부터	2	-3	-6	-1	3	1	-2	4
-1부터	-2	3	6	1	-3	-1	2	-4

 

이제 여기서 누적합을 시도해보자

 

2	-1	-7	-8	-5	-4	-6	-2
-2	1	7	8	5	4	6	2

 

누적합의 정의상 각 구간의 합을 빠르고 간편하게 구할 수 있다. -1부터 펄스를 더했을 때 prefix[4] = 8 에서 8보다 아래 있는 누적합 중 음수가 있다면 그것을 제외해준다면 8 - (-2) 로 10으로 답을 구할 수있다.

 

1부터 시작한 펄스와 -1부터 시작한 펄스 둘 다 같은 방식으로 해보면 된다.

 

개인적으로 요즘 누적합을 공부중인데 마침 이 문제를 만났고 눈치챘다는 사실에 기분이 좋다. 파이팅!!

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long prefix1[500001];
long long prefix2[500001];

long long solution(vector<int> sequence) {
    long long answer = 0;
    int purse1 = 1;
    int purse2 = -1;
    for(int i = 1; i < sequence.size() + 1; i++){
        prefix1[i] = prefix1[i - 1] + sequence[i - 1] * purse1;
        prefix2[i] = prefix2[i - 1] + sequence[i - 1] * purse2;
        
        purse1 *= -1;
        purse2 *= -1;
    }
    
    int prefixIdx1 = -1;
    long long prefixValue1 = 0;
    for(int i = 1; i <= sequence.size(); i++){
        if(prefixValue1 <= prefix1[i]){
            prefixValue1 = prefix1[i];
            prefixIdx1 = i;
        }
    }
    long long prefix1Ans = prefixValue1;
    for(int i = 1; i < prefixIdx1; i++){
        if(prefix1[i] < 0){
            if(prefix1Ans < prefixValue1 - prefix1[i]){
                prefix1Ans = prefixValue1 - prefix1[i];
            }
        }
    }
    
    int prefixIdx2 = -1;
    long long prefixValue2 = 0;
    for(int i = 1; i <= sequence.size(); i++){
        if(prefixValue2 <= prefix2[i]){
            prefixValue2 = prefix2[i];
            prefixIdx2 = i;
        }
    }
    long long prefix2Ans = prefixValue2;
    for(int i = 1; i < prefixIdx2; i++){
        if(prefix2[i] < 0){
            if(prefix2Ans < prefixValue2 - prefix2[i]){
                prefix2Ans = prefixValue2 - prefix2[i];
            }
        }
    }
    
    answer = max(prefix1Ans, prefix2Ans);
    
    return answer;
}