[programmers/c++] 풀이 기록 - 연속 펄스 부분 수열의 합

문제

프로그래머스

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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의 원소는 정수입니다.

 

1. 단순 3중 for문

-1, 1, -1.. 순서로 곱한 벡터와 1,-1,1..순서로 곱한 벡터 두개를 만든 후, 각 벡터별로 무식하게 3중 for문 돌면서 모든 가능한 부분배열의 합을 구해 최솟값을 확인해보았다.

long long sum = 0;
long long tempSum = 0;

int listSize = sequence.size();
for(int i = 0; i < listSize; i++){
    for(int j = i; j < listSize; j++){
        tempSum = 0;
        for(int k = i; k <= j; k++){
            tempSum += sequence[k];    
        }
        sum = max(tempSum, sum);   
    }     
}

결과는 당연하게도 테스트케이스 10번부터 모두 시간초과..

테스트 8 〉 통과 (21.90ms, 4.22MB)
테스트 9 〉 통과 (120.00ms, 4.14MB)
테스트 10 〉 실패 (시간 초과)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)

 

2. 배열 축소 후 3중 for문

양수가 연속되는경우는 모든 양수를 포함하는것이 최대가 될 것이다. 음수가 연속되는 경우또한 해당 음수 그룹을 포함하고 다음 양수를 포함하던지, 혹은 해당 음수 그룹을 포함하지 않던지 두가지 밖에 선택할 수 없다.

따라서 연속되는 양수와 연속되는 음수는 모두 합하여, 좀더 짧은 배열로 변경 후 동일하게 3중 for문을 돌리도록 수정해보았다.

int listSize = sequence.size();
vector<long long> shortList;
shortList.reserve(listSize);
for(int i = 0; i < listSize; i++)
{
    // +, -, +, -,...
    if(tempSum*sequence[i] < 0){
        //shortList[0] is always positive
        if((shortList.empty()==false) || (tempSum>0)){
            shortList.push_back(tempSum);
        }
        tempSum = sequence[i];
    }else{
        tempSum += sequence[i];
    }
    //last item(+)
    if((i == sequence.size()-1)&&(tempSum>0))
        shortList.push_back(tempSum);
}

int shortListSize = shortList.size();
for(int i = 0; i < shortListSize; i+=2){
    if((i < shortListSize-1)&&(shortList[i] + shortList[i+1]) <= 0)
        continue;
    for(int j = shortListSize-1; j >= i; j-=2){   
        if((j>1)&&(shortList[j] + shortList[j-1]) <= 0)
            continue;
        tempSum = 0;
        for(int k = i; k <= j ; k++)
            tempSum += shortList[k];
        sum = max(tempSum, sum);
    }
}

결과는 조금 개선되었으나, 여전히 시간 초과 문제가 발생하였다.

테스트 10 〉 통과 (22.59ms, 3.77MB)
테스트 11 〉 통과 (183.13ms, 4.15MB)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 실패 (시간 초과)
테스트 14 〉 실패 (시간 초과)
테스트 15 〉 실패 (시간 초과)
테스트 16 〉 통과 (0.91ms, 7.67MB)
테스트 17 〉 실패 (시간 초과)
테스트 18 〉 실패 (시간 초과)
테스트 19 〉 통과 (4.44ms, 24.8MB)
테스트 20 〉 통과 (4.97ms, 24.7MB)

 

3. 양 끝부터의 최소 부분합 구하기

좋은 방법이 없을 지 한참을 생각하다보니, 첫번째 혹은 마지막 부터 시작하여 최솟값을 가지는 부분합을 구하여 전체합에서 빼는건 어떨까 하는 아이디어가 떠올랐다.

두개의 최솟값 부분합을 구하여 전체합에서 빼도록 구현해보았다. 

첫번째 인덱스부터 최소 부분합 구하는것, 마지막 인덱스부터 최소값 부분합 구하는것, 전체배열의 합 구하는 것 모두 O(n)으로 가능하다.

long long getMaxNagativeSum(const vector<int>& sequence){
    int listSize = sequence.size();
    long long sum(0), minimumSum(0);
    int minimumIdx(0);
    for(int i = 0; i < listSize; i++){
        sum += sequence[i];
        if(sum <= minimumSum){
            minimumSum = sum;
            minimumIdx = i;
        }
    }    
    sum = minimumSum;
    for(int i = listSize-1; i > minimumIdx; i--){
        sum += sequence[i];
        if(sum <= minimumSum)
            minimumSum = sum;
    }
    return minimumSum;
}

수정 결과 성능이 매우 좋아졌으나, 테스트케이스 17번이 실패하는 문제가 있었다.

테스트 16 〉 통과 (1.24ms, 7.46MB)
테스트 17 〉 실패 (5.50ms, 24.4MB)
테스트 18 〉 통과 (5.90ms, 24.3MB)

 

버그수정

[2,  3, -6,  1, 3, -1, 2,  4]
[2, -3, -6, -1, 3,  1, 2, -4] => sum:-6
[-2, 3,  6,  1, -3, -1, -2, 4] => sum:6

위와같이 특정 배열에 [1, -1, 1, -1,...] 를 곱한 배열과 [-1, 1, -1, 1...] 를 곱한 배열은 절대값이 같고 반대의 부호를 가진다는 점을 확인하였었다. 

그래서 합이 양수인 배열이 최대 부분합을 가질것이라 생각해서, 그 배열만 가지고 계산을 하도록 했었다.

[2,  3, -6,  1, 5, -1,  5,  4]
[2, -3, -6, -1, 5,  1,  5, -4] => sum:-3
[-2, 3,  6,  1, -5, -1, -5, 4] => sum:3

하지만 위와같은 케이스의 경우, 합이 음수인 배열에 최대 부분합이 있다는 사실을 발견하였다.

따라서 양쪽 배열 모두 최댓값을 확인하도록 수정하였고 모든 테스트에 통과하였다.

 

테스트 1 〉 통과 (0.01ms, 4.16MB)
테스트 2 〉 통과 (0.01ms, 4.15MB)
테스트 3 〉 통과 (0.01ms, 4.16MB)
테스트 4 〉 통과 (0.01ms, 3.64MB)
테스트 5 〉 통과 (0.01ms, 4.15MB)
테스트 6 〉 통과 (0.01ms, 4.22MB)
테스트 7 〉 통과 (0.01ms, 4.03MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.02ms, 4.21MB)
테스트 10 〉 통과 (0.05ms, 4.14MB)
테스트 11 〉 통과 (0.10ms, 4.09MB)
테스트 12 〉 통과 (1.32ms, 7.21MB)
테스트 13 〉 통과 (1.36ms, 7.2MB)
테스트 14 〉 통과 (1.01ms, 7.38MB)
테스트 15 〉 통과 (0.96ms, 7.26MB)
테스트 16 〉 통과 (1.33ms, 7.46MB)
테스트 17 〉 통과 (5.80ms, 24.5MB)
테스트 18 〉 통과 (6.92ms, 24.3MB)
테스트 19 〉 통과 (5.08ms, 24.6MB)
테스트 20 〉 통과 (7.10ms, 24.5MB)

 

4. 동적계획법(다른사람의 풀이)

다른사람의 풀이 보기에서 첫번째로 나온 내용을 보았는데, 코드가 10줄 정도로 짧은 것을 보고 조금 충격을 받았다. 성능또한 3번방법으로 한것과 거의 유사했다.

이외에 다른 풀이를 보아도 대체로 유사한 방법으로 문제를 해결한것처럼 보였다.

공통적으로 보이는 변수이름이 dp인데, 이를 찾아보니 동적계획법(Dynamic Programming)이라는 방법론으로, "큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용" 하는것 이라고한다. 

const int n = sequence.size();
long long answer = abs(sequence[0]);
vector<pair<long long,long long>> dp(n);
dp[0].first = sequence[0];
dp[0].second = -sequence[0];    
for(int i = 1; i < n; ++i){
    dp[i].first = max((long long)(sequence[i]), sequence[i] + dp[i-1].second);
    dp[i].second = max((long long)(-sequence[i]), -sequence[i] + dp[i-1].first);
    answer = max(answer,max(dp[i].first,dp[i].second));
}

index를 돌면서 현재값(sequence[i])과 dp에 저장해둔 이전값+현재값(sequence[i]+dp[i-1]) 중 더 큰값을 dp[i]에 저장해둔다.

- 양수값이 연속되면 dp배열에 누적합이 계속 쌓일 것이다.(누적합+현재값 > 현재값)

- 이후 음수값이 나왔을때도 만약 누적합이 현재값 보다 크다면 계속 누적합을 사용한다.(누적합+현재값 > 현재값)

- 음수값이 계속 연속되어 누적합이 음수로 작아진 상태에서 양수값이 나온다면, dp가 누적값을 버리고 새로운값으로 교체된다.(누적합+현재값 < 현재값)

- 음수값이 계속 연속되어 누적합이 계속 작아졌지만 양수를 유지한 상태에서는, 새로운 양수가 나오더라도 누적합에 더하는 편이 더 크기때문에 누적합을 계속 사용한다.(누적합+현재값 > 현재값)

 

위와같은 규칙에 의해 중간 부분의 음수 배열을 포함할지말지를 결정할 수 있게된다. 

앞서 고민했던 2.배열축소후 3중 for문 단계에서 조금만 더 깊이 생각해보았다면 근접했을 수도 있지만 아쉽게도 전혀 생각하지 못했다.

 

 

 

동적계획법에 대해서 분명히 학부생때 배웠을테지만, 졸업한지 한참이 지나 알고리즘 문제를 풀고있는 지금은 완전히 새로운 이론같이 느껴진다.

점점 많은 문제를 풀어보면서 잊고있던것들을 새롭게 배우고, 새로운 문제를 대면했을때 그 지식을 이용할 수 있게 되었으면 좋겠다.