[C/C++] programmers Level 2 연속된 부분 수열의 합

 

 

 

 

코드

 

#include <vector>
#include <queue> // 큐

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    
    vector<int> answer(2,0); // 0~1 범위 0값
    queue<pair<int,int>> q; // pair<int, int> -> 구조체 대신 사용 더 사용하기 편함 
    // pair<int, int> -> int : sequence값, int : sequence 인덱스 값
    int sum=0; // k 비교를 위한 합값
    int size=sequence.size()+1; // q.size 비교 값
    
    for(int i=0;i<sequence.size();i++){
        q.push({sequence[i],i});
        sum=sum+sequence[i];
        
        while(k<sum){ // 큐 사용을 통한 연속된 부분 수열 연산 -> sum이 k보다 작아지거나 같아질때 까지 반복 수행
            
            sum=sum-q.front().first;
            q.pop();
        }
        
        if(sum==k && q.size()<size){ // 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾기 위한 q.size와 size 비교
            answer[0]=q.front().second;
            answer[1]=q.back().second;
            
            size=q.size();
        }
    } 
    
    return answer;
}