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

연속된 부분 수열의 합

문제 링크

연속된 부분 수열의 합

분석

수열에서 원소의 합이 k가 되는 가장 짧은 구간의 시작 인덱스와 끝 인덱스를 찾아 반환해야합니다.
하지만, 여러 개의 부분 수열이 k와 같다면 시작 인덱스가 작은 것을 반환해야합니다.

이중 반복문은 최대 $1,000,000 \times 1,000,000$이므로, 시간 초과가 날 수 있습니다.

풀이

#include <string>
#include <vector>
#include <climits>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int leftPointer = 0;    // 시작 인덱스
    int rightPointer = 0;   // 끝 인덱스
    int minLength = INT_MAX;    // 최소 길이 저장
    
    int sum = sequence[0];  // 현재 부분합
    
    // 끝 인덱스를 기준으로 sequence를 반복
    while(rightPointer < sequence.size())
    {
        // 현재 부분합이 k보다 작은 경우
        if (sum < k)
        {
            ++rightPointer;
            sum += sequence[rightPointer];
        }
        // 현재 부분합이 k보다 큰 경우
        else if (sum > k)
        {
            sum -= sequence[leftPointer];
            ++leftPointer;
        }
        // 현재 부분합이 k와 같은 경우
        else
        {
            // 현재 길이
            int length = rightPointer - leftPointer;
            
            // 최소 길이가 현재 길이보다 큰 경우 값 갱신
            if(minLength > length)
            {
                minLength = length;
                answer = {leftPointer, rightPointer};
            }
            
            // 다음 탐색을 위해 시작 인덱스를 다음 인덱스로 변경
            sum -= sequence[leftPointer];
            ++leftPointer;
        }
    }
    
    return answer;
}

투 포인터를 사용하고, 두 포인터는 시작 인덱스와 끝 인덱스를 의미합니다.

현재 부분합이 k보다 작다면, right의 크기를 증가시키면서 부분합을 증가시킵니다.
현재 부분합이 k보다 크다면, left의 크기를 증가시키면서 부분합을 감소시킵니다.
현재 부분합이 k와 같다면, 현재 길이보다 짧은지 확인하고 값을 갱신합니다.

성능 요약

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

• 끝 인덱스를 기준으로 sequence를 반복 $O(n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.22MB)
테스트 2 〉 통과 (0.03ms, 4.15MB)
테스트 3 〉 통과 (0.01ms, 4.15MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.06ms, 4.17MB)
테스트 6 〉 통과 (0.10ms, 4.3MB)
테스트 7 〉 통과 (0.30ms, 4.94MB)
테스트 8 〉 통과 (0.57ms, 6.58MB)
테스트 9 〉 통과 (1.02ms, 9.98MB)
테스트 10 〉 통과 (3.04ms, 19.7MB)
테스트 11 〉 통과 (5.12ms, 36.1MB)
테스트 12 〉 통과 (7.39ms, 36.2MB)
테스트 13 〉 통과 (5.37ms, 36.2MB)
테스트 14 〉 통과 (7.99ms, 36.2MB)
테스트 15 〉 통과 (8.09ms, 36.3MB)
테스트 16 〉 통과 (3.92ms, 36.8MB)
테스트 17 〉 통과 (6.48ms, 36.7MB)
테스트 18 〉 통과 (0.01ms, 4.02MB)
테스트 19 〉 통과 (0.01ms, 3.67MB)
테스트 20 〉 통과 (0.01ms, 3.59MB)
테스트 21 〉 통과 (0.01ms, 4.22MB)
테스트 22 〉 통과 (0.01ms, 3.68MB)
테스트 23 〉 통과 (0.01ms, 3.67MB)
테스트 24 〉 통과 (4.66ms, 34.6MB)
테스트 25 〉 통과 (3.55ms, 34.7MB)
테스트 26 〉 통과 (5.13ms, 34.6MB)
테스트 27 〉 통과 (5.27ms, 34.6MB)
테스트 28 〉 통과 (4.36ms, 34.7MB)
테스트 29 〉 통과 (4.49ms, 34.6MB)
테스트 30 〉 통과 (5.17ms, 36.7MB)
테스트 31 〉 통과 (0.01ms, 3.69MB)
테스트 32 〉 통과 (0.01ms, 4.21MB)
테스트 33 〉 통과 (0.01ms, 4.22MB)
테스트 34 〉 통과 (0.01ms, 4.2MB)