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

1. 문제

• 비내림차순 수열과 목표에 해당하는 값 k 제공
• 수열에서 원소와 원소 사이의 값들을 모두 합한 부분 수열의 합이 k인 인덱스를 탐색
• 인덱스 사이의 길이가 짧은 것이 우선

2. 풀이

1. 비내림차순의 정렬된 수열 ㅡ> 뒤로 갈수록 같거나 큰 수 등장
2. 수열에서 부분 수열의 시작, 종료 지점의 인덱스를 조절하며 k값 탐색 (투 포인터)
3. 시작, 종료 인덱스 사이의 부분 수열의 합이 k 미만 ㅡ> 종료 인덱스 증가
4. 시작, 종료 인덱스 사이의 부분 수열의 합이 k 초과 ㅡ> 시작 인덱스 증가
5. 시작, 종료 인덱스 사이의 부분 수열의 합이 k와 동일 ㅡ> 인덱스 사이의 거리가 최소인지 판별
6. 인덱스 사이의 거리가 최소라면 해당 인덱스 값으로 업데이트

3. 코드

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    int start=0, end=0, sum=sequence[0], len=sequence.size();
    int MinLength=INT_MAX;
    pair<int,int> proper={-1,-1};
    
    while(end<len)
    {
        if(sum<k)
        {
            ++end;
            if(end<len) sum+=sequence[end];
        }
        else
        {
            if(sum==k)
            {
                int length=end-start+1;
                if(length<MinLength)
                {
                    MinLength=length;
                    proper={start,end};
                }
            }
            sum-=sequence[start];
            ++start;
        }
    }
    return {proper.first,proper.second};
}

• 시작 : start, 끝 : end 로 각각의 인덱스를 가리키는 변수 선언 및 0으로 초기화
• 부분 수열의 합을 저장할 변수 sum 선언 및 수열의 첫번째 원소로 초기화
• 최소 거리를 저장할 변수 MinLength 초기화
• pair<int, int> proper를 선언해 지속적으로 최소 거리의 부분 수열 인덱스 값으로 업데이트
• 나머지 풀이에서의 흐름과 동일

---

문제 링크

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

프로그래머스