문제 178870. 연속된 부분 수열의 합

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

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

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

입력

• 수열을 나타내는 정수 배열 sequence
• 부분 수열의 합을 나타내는 정수 k

입력 제한

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

입력 예제

// input
[1, 2, 3, 4, 5] // sequence
7               // k

// ans
[2, 3]

 

풀이 방식

 이 문제는 비내림차순으로 정렬된 수열이 주어질 때, 합이 k가 되는 부분 수열을 구하면 된다. 여러 경우의 수가 나오는 경우, 가장 길이가 짧은 수열을 구하면 되는데, 이를 구하기 위해서 필자는 지렁이 전략을 고안해냈다.

 

지렁이 전략

지렁이는 본인의 일자로 된 몸을 수축하고 다시 늘리면서 간다. 이처럼 이번 문제를 풀 때 지렁이처럼 부분 수열의 길이를 수축하고 늘리며 배열의 마지막 인덱스까지 이동할 것이다.(가능하다면) 아래 예시는 입력 예제를 통해 푼 방식이다.

 

예시

 

우선, 부분수열의 시작과 끝을 배열의 첫번째 위치로 한다.

• 시작 idx: 0, 끝 idx: 0, 부분 수열: [1], 부분 수열의 합: 1

 

부분 수열의 합이 k보다 작으면(이 예제에서 k는 7이다), 끝 인덱스를 이동시킨다.

• 시작 idx: 0, 끝 idx: 1  부분 수열: [1, 2], 부분 수열의 합: 3
• 시작 idx: 0, 끝 idx: 2  부분 수열: [1, 2, 3], 부분 수열의 합: 6
• 시작 idx: 0, 끝 idx: 3  부분 수열: [1, 2, 3, 4], 부분 수열의 합: 10

 

부분 수열의 합이 k보다 크면, 시작 인덱스를 이동시킨다.

• 시작 idx: 1, 끝 idx: 3  부분 수열: [2, 3, 4], 부분 수열의 합: 9

 

부분 수열의 합이 k와 같다면 시작 인덱스와 끝 인덱스를 통해 부분 수열의 길이를 구한다.

• 시작 idx: 2, 끝 idx: 3  부분 수열: [3, 4], 부분 수열의 합: 7

 

더 이상 부분 수열을 만들 수 없을 때까지 반복한다.

• 시작 idx: 2, 끝 idx: 4  부분 수열: [3, 4, 5], 부분 수열의 합: 12
• 시작 idx: 3, 끝 idx: 4  부분 수열: [4, 5], 부분 수열의 합: 9
• 시작 idx: 4, 끝 idx: 4  부분 수열: [5], 부분 수열의 합: 5
• 시작 idx: 5, 끝 idx: 4  부분 수열: [], 부분 수열의 합: 0

정답 코드 

#include <bits/stdc++.h>

#define MAXLEN 1'000'001

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int ans_s = -1, ans_e = MAXLEN;
    int start = 0, end = 0;
    int sum = sequence[0];
    
    do{
        // 부분 수열의 합이 작았다면, end를 1칸 이동시키고 end 위치의 원소 값을 sum에 더한다.
        if(sum < k){
            end++;
            sum += sequence[end];                
        }
        // 부분 수열의 합이 작지 않았다면, start를 1칸 이동시키고 start 위치의 원소 값을 sum에서 뺀다.
        // 만약 부분 수열의 합이 같았다면, 해당 start와 end값을 부분 수열의 길이가 작았을 때 정답으로 저장한다.
        else{
            if(sum == k && (end - start < ans_e - ans_s)){
                ans_s = start;
                ans_e = end;
               
            }
            sum -= sequence[start];   
            start++;
        }
        
    }
    while(start <= end && end < sequence.size());
        
    answer = {ans_s, ans_e};
    
    return answer;
}