[프로그래머스] 연속된 부분 수열의 합 (C++)

👓 문제 설명

---

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

---

💣 제한 사항

• 5 ≤ sequence의 길이 ≤ 1,000,000
  • 1 ≤ sequence의 원소 ≤ 1,000
  • sequence는 비내림차순으로 정렬되어 있습니다.
• 5 ≤ k ≤ 1,000,000,000
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

---

🚨 접근 방법

처음에는 DP를 이용하여 단순 계산으로 문제를 풀어보았다. 아니나 다를까 for문이 2번 돌면서 시간초과가 발생했다. 어떤 알고리즘을 써야할까 고민하던 중 이전에 백준에서 비슷한 문제를 풀었던 기억이 났다. 시작, 끝 두 지점을 0번 인덱스부터 시작하고 구하려는 값보다 작으면 end + 1, 크면 start + 1 방법으로 두개의 지점을 함께 이동시키는 알고리즘인 투포인터 알고리즘을 사용하면 될 것 같았다.

이 문제 같은 경우
sum < k -> end + 1, sum에 sequence[e]를 더하기
sum == k -> 두가지 경우로 나누어서 answer 갱신하기, sum에 sequence[s]를 빼고 start -1
sum > k -> start + 1

---

🚈 풀이

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

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer(2,0); // 0으로 초기화된 2개의 원소를 갖는 벡터
    int s=0,e=0;
    int sum=sequence[0];
    int sublen=sequence.size()+1;
    while(s<=e&&e<sequence.size()){
        if(sum<k){
            sum+=sequence[++e];
        }
        else if(sum==k){
            int len=e-s;
            // 부분 문자열의 길이가 더 짧은 경우 갱신
            if(sublen>len){
                sublen=len;
                answer[0]=s;
                answer[1]=e;
            }
            // 부분 문자열의 길이가 같으나 더 작은 시작 인덱스 값으로 갱신
            else if(sublen==len){
                if(answer[0]>s){
                    answer[0]=s;
                    answer[1]=e;
                }
            }
            sum-=sequence[s++];
        }
        else{
            
            sum-=sequence[s++];
        }
    }
    return answer;
}