[프로그래머스] 연속된 부분 수열의 합 C++ 풀이 및 해설

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

프로그래머스

풀이 방법

왼쪽과 오른쪽 인덱스와 현재 수열 총 합 sum을 가지고 결과를 찾아간다.

처음 왼쪽과 오른쪽 인덱스는 시작 인덱스 0을 가지고

sum은 0번째 인덱스 값을 가지고 시작한다.

 

1. sum<k라면
   1. 끝 인덱스를 1 더하고 범위를 벗어나지 않는다면 sum+="끝 인덱스에 있는 값"을 해준다.
2. sum>k라면
   1. 현재 시작 인덱스에 있는 값을 sum에서 빼주고 시작 인덱스를 1 증가한다.
3. sum==k라면
   1. 길이가 현재 최소 길이 len보다 짧다면 결과가 될 수 있다.
   2. 최소 길이보다 짧다면 결과 시작 인덱스와 끝 인덱스를 갱신해주자.
   3. 뒤에 더 짧은 길이로 만들 수 있을지 모르니 끝 인덱스를 하나 증가시키고 인덱스에 값이 있다면 sum에 더해주자

위의 1 2 3 과정을 start가 end를 넘어설때까지 반복하면 된다.

로직에 end의 위치를 한칸씩 뒤로 옮겨 계산하는 과정이 있으므로 while문의 조건문에 항상 end의 위치를 벗어나지 않는지 확인하자.

 

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int start = 0; // 시작 인덱스
    int end = 0; // 마지막 인덱스
    
    int resStart = 0; // 결과 후보 시작 인덱스
    int resEnd = 0;
    int len = 1000001; // 현재 최소 길이
    int sum=sequence[0]; // 수열 합
    
    while(start<=end && end<sequence.size()) {
        if(sum<k) {
            end++;
            if(end<sequence.size()) {
                sum+=sequence[end];
            }
        } else if (sum>k) {
            sum-=sequence[start];
            start++;
        } else { // sum == k
            if(end-start+1<len) { // 현재 최소 길이보다 더 짧다면
                len = end-start+1;
                resStart = start;
                resEnd = end;
            }
            end++;
            sum+=sequence[end];
        }
    }
    answer.push_back(resStart);
    answer.push_back(resEnd);
    return answer;
}