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

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/178870

풀이

---

비 내림차순으로 정렬된 수열에서 주어진 조건을 충족하는 부분 수열을 찾는 문제로, 투 포인터를 사용하여 풀이하였다. 부분 수열의 합이 k이면서 제일 짧고, 제일 앞에 있는 수열을 찾기 위해 두 포인터를 사용, 두 포인터가 가리키는 구간의 합이 k보다 작으면 end 포인터를 이동하고, k보다 크면 start 포인터를 이동, k와 같은 합이 나오면 길이 비교 후 저장을 결정한다. 이를 end 포인터가 주어진 수열의 끝에 이동할 때까지 이를 반복하여 나온 구간의 길이를 return한다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k)
{
    vector<int> answer(2);

    answer[0] = 0;
    answer[1] = 1000000;

    int start = 0;
    int end = 0;
    int sum = sequence[0];

    while (end < sequence.size())
    {
        if (sum < k)
        {
            end++;
            if (end < sequence.size()) sum += sequence[end];
        }

        else if (sum > k)
        {
            sum -= sequence[start];
            start++;
        }

        else if (sum == k)
        {
            if (answer[1] - answer[0] > end - start)
            {
                answer[0] = start;
                answer[1] = end;
            }

            sum -= sequence[start];
            start++;
            end++;
            if (end < sequence.size()) sum += sequence[end];
        }
    }

    return answer;
}