C++:: 프로그래머스 <연속된 부분 수열의 합>

처음에는 수열의 합을 저장해놓은 dp를 활용하여 이중 for문을 돌며 풀었는데 시간초과가 나서 다른 방법이 무엇이 있을까 고민하다가 queue를 활용하여 풀면 쉽겠다 생각하고 풀었다. 다른 사람들의 풀이를 보면 이중for문으로도 최적화를 잘하면 충분히 풀 수 있는 문제인듯 싶지만 queue를 활용한 풀이를 유도한 문제처럼 보인다.

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(vector<int> sequence, int k)
{
    vector<int> answer(2,0);
    queue<pair<int,int>> q;
    int n = sequence.size(), len = 1000001, sum = 0;
    for(int i=0;i<n;i++)
    {
        q.push({sequence[i], i});//큐에 넣어준다.
        sum += sequence[i];//큐에 들어있는 수 합 ++
        while (sum > k)
        {// 큐에 들어있는 수의 합이 k보다 작거나 같을때 까지
            sum -= q.front().first;// 먼저 들어온 수 합에서 빼주고
            q.pop();// 큐에서도 빼준다.
        }
        if (sum == k && q.size() < len)
        {// 큐에 들어있는 수열의 합이 k이고 이전 결과의 길이보다 짧다면
            len = q.size();//길이 갱신
            answer[0] = q.front().second;// 시작 인덱스
            answer[1] = q.back().second;// 끝 인덱스
        }
    }
    return answer;
}