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

연속 펄스 부분 수열의 합

문제 링크

연속 펄스 부분 수열의 합

분석

펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …]과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.

연속 펄스 부분 수열의 합 중 가장 큰 것을 반환해야합니다.

연속 부분 수열의 시작점

풀이

#include <vector>
#include <algorithm>

using namespace std;

// 카데인 알고리즘을 이용해 연속 부분 수열의 최대 합을 구하는 함수
long long maxSubsequenceSum(const vector<long long>& pulse)
{
    long long maxSum = pulse[0];     // 지금까지의 최대 연속 부분 수열 합
    long long currentSum = pulse[0]; // 현재 위치까지의 연속 부분 수열 합
    
    for (int i = 1; i < pulse.size(); ++i)
    {
        // 현재 원소 하나만 사용하는 것이 나은지, 이전까지의 합에 더하는 것이 나은지 선택
        currentSum = max(pulse[i], currentSum + pulse[i]);

        // 최대값 갱신
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

long long solution(vector<int> sequence) {
    long long answer = 0;
    
    // 두 종류의 펄스 수열을 저장할 벡터
    vector<long long> pulse1(sequence.size());
    vector<long long> pulse2(sequence.size());
    
    // 입력된 sequence에 펄스 수열을 곱하여 변형된 수열 생성
    for (int i = 0; i < sequence.size(); ++i)
    {
        // 짝수 인덱스는 양수, 홀수 인덱스는 음수
        pulse1[i] = sequence[i] * ((i % 2 == 0) ? 1 : -1);

        // 짝수 인덱스는 홀수, 짝수 인덱스는 양수
        pulse2[i] = sequence[i] * ((i % 2 == 0) ? -1 : 1);
    }
    
    // 각 펄스 수열에 대해 최대 연속 부분 수열 합 계산
    long long maxSum1 = maxSubsequenceSum(pulse1);
    long long maxSum2 = maxSubsequenceSum(pulse2);
    
    answer = max(maxSum1, maxSum2);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 변형된 수열 생성하는 반복문 $O(n)$
• 카데인 알고리즘 $O(n)$
• $O(n) + O(n) + O(n)$

공간 복잡도는 $O(n)$입니다.

• 변형된 수열을 저장하는 벡터 $O(n)$
• $O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 3.91MB)
테스트 2 〉 통과 (0.01ms, 3.68MB)
테스트 3 〉 통과 (0.01ms, 4MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.17MB)
테스트 6 〉 통과 (0.01ms, 3.66MB)
테스트 7 〉 통과 (0.01ms, 4.11MB)
테스트 8 〉 통과 (0.01ms, 3.71MB)
테스트 9 〉 통과 (0.02ms, 4.21MB)
테스트 10 〉 통과 (0.08ms, 4.21MB)
테스트 11 〉 통과 (0.15ms, 4.21MB)
테스트 12 〉 통과 (1.79ms, 8.1MB)
테스트 13 〉 통과 (1.50ms, 8.06MB)
테스트 14 〉 통과 (1.49ms, 8.09MB)
테스트 15 〉 통과 (1.32ms, 8.13MB)
테스트 16 〉 통과 (1.55ms, 8.23MB)
테스트 17 〉 통과 (6.86ms, 27.9MB)
테스트 18 〉 통과 (7.41ms, 28.2MB)
테스트 19 〉 통과 (6.55ms, 28.3MB)
테스트 20 〉 통과 (6.43ms, 28.4MB)