연속된 부분 수열의 합

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

윈도우 슬라이딩으로 푸는 문제이다.

초기화 되었을 때는 이런 상태로 되어있다.

 

이 상태에서 RIGHT위치의 값을 SUM에 더한다.

 

만약, SUM이 이보다 작다면? 비내림차순 정렬이므로 다음 값을 윈도우에 포함시켜준다. 그러면 아래와 같은 모양이 된다.

 

 

이 상태에서 여전히 임의의 정수 N이 k보다 작다면 위 과정을 반복한다.

 

 

그러다보면 아래 그림과 같이 k값을 넘게 된다.

 

그럴 때는 이렇게 LEFT를 한 칸 증가시켜 윈도우 내부의 값을 줄인다.

상기의 과정을 반복하며 조건을 만족하는 윈도우 중 지금까지 등록된 가장 짧은 윈도위의 LEFT와 RIGHT를 기록하게 해두었다 출력하도록 구현하면 된다.

#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer(2, 0);
    int left = 0, right = 0, sum = 0;
    int min_len = sequence.size() + 1;  // 가능한 부분 수열의 길이보다 큰 값으로 초기화

    while (right < sequence.size()) {
        sum += sequence[right];
        
        while (sum > k && left <= right) {
            sum -= sequence[left];
            left++;
        }

        if (sum == k && (right - left + 1) < min_len) {
            answer[0] = left;
            answer[1] = right;
            min_len = right - left + 1;
        }

        right++;
    }


    return answer;
}