[Programmers] 프로그래머스 Lv.2 연속된 부분 수열의 합 문제풀이(C++)

중요한 부분 : sequence 배열을 참조하며 선형적으로 start_index, end_index만 변화시키면서 sum을 관리하면 시간 내에 해결 가능

 

처음에 배열 생성해서 push_back, erase 해주면서 진행하니까 시간초과떴음

#include <string>
#include <vector>
#include<iostream>
using namespace std;
/*
<문제>
수열이 있음 - 비내림차순(중복가능한 오름차순)
여기서 합이 k인 연속된 부분수열 추출
  1. 길이가 짧은 수열
  2. 길이가 같으면, 앞부분 수열
 
조건을 만족하는 부분수열의 첫, 끝 인덱스 담아서 리턴
 
sequence 길이 <= 100만
k <= 10억
k는 항상 sequence의 부분수열로 만들 수 있는 값
 
 
<풀이>
start_index, end_index 변수 생성(둘다 0 초기화) / sum 생성(k가 10억 이하이므로 long long int 필요없음)
합이 넘어가면 start_index++; 합보다 적으면 end_index++; 합이 k이면, 해당 시작/끝 인덱스 기록
각 단계별 sum 계산 잘해주기
 
<시간>
한번 탐색으로 가능 - O(2*sequence)
*/
vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    int start_index = 0, end_index = 0; //시작, 끝 인덱스
    int s = -1, e = -1;    //여기에 답 저장
    int sum = sequence[0];  //numlist 모든 수 합
 
    while (start_index <= end_index && end_index < sequence.size()) {
        if (sum < k) {
            end_index++; if (end_index >= sequence.size()) continue;
            sum += sequence[end_index];
        }
        else if (sum > k) {      
                sum -= sequence[start_index];    
                start_index++;  //시작인덱스 업데이트            
        }
        else {   //sum == k
            if (e == -1) { s = start_index; e = end_index;  }   //처음 발견 
            else if (e - s > end_index - start_index) { s = start_index; e = end_index; }
            
            //저장 후 끝 인덱스 추가
            end_index++; if (end_index >= sequence.size()) continue;
            sum += sequence[end_index];
        }
    }
    answer.push_back(s); answer.push_back(e);
    return answer;
}