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

이 포스트는 프로그래머스 사이트의 연속된 부분 수열의 합 문제 풀이입니다.

문제

해결 과정

이 문제를 처음 접한다면 sequence 범위에서 순환하는 2중 반복문을 시도해 볼 수 있습니다.
그러나 문제에서 sequence의 길이로 1’000’000이 될 수 있다고 하였습니다.
만약, 1’000’000이 주어진다면 2중 반복문에서는, 1’000’000’000’000 만큼 연산하기 때문에
제한 시간 안에 풀 수 없습니다.
따라서 2중 반복문이 아닌 방법을 사용해서 연속된 배열의 합을 구해야 합니다.

문제에서 제공되는 정보는 아래와 같습니다.

1. 연속된 부분 수열의 합 구하기
2. 구한 합 중 값이 k인 부분 수열 구하기
3. 1, 2번을 충족하는 부분 수열이 여럿 있는 경우, 0번 인덱스와 가까운 부분 수열을 선택

위 3가지 정보를 토대로 우선 연속된 합이라는 키워드로 누적합 알고리즘을
사용해 풀 수 있다는 힌트를 얻을 수 있습니다.
그리고 3번의 설명처럼 합이 k가 되는 부분 수열이 여럿 있을 수 있으므로
조건을 만족하는 부분 수열의 범위를 저장하고 비교하면 정답을 구할 수 있습니다.

제출 코드

#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    // i: 좌측 인덱스, j: 우측 인덱스, min_len: 합이 k인 부분 수열의 최소 길이
    int i = 0, j = 0, min_len = 2e9;
    int sum = sequence[0];
    
    while(j < sequence.size()) {
        if (sum < k) {
            sum += sequence[++j];
        }
        else if (sum > k) {
            sum -= sequence[i++]; // [주의] ++ 연산자는 위치에 따라 내용이 다름.
        }
        else { // sum == k
            if(j - i < min_len) {
                min_len = j - i;
                answer = {i, j};
            }
            sum -= sequence[i++];
        }
    }
    return answer;
}

제출 결과