[프로그래머스] 연속된 부분 수열의 합 - 투 포인터

[ 문제링크 ]

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

 

🚩 조건

1. 비내림차순(=오름차순) 수열 sequence와 k가 주어지면, 합이 k인 부분 수열을 찾아라
2. 부분 수열 중 가장 길이가 짧은 것을 찾되, 길이가 같으면 먼저 등장하는 것을 찾아라
3. 5 ≤ sequence의 길이 ≤ 1,000,000
4. 5 ≤ k ≤ 1,000,000,000 / k는 항상 부분수열의 합으로 나올 수 있는 정수

 

 

🚩 접근

for문으로 앞 원소부터 더해나가다가 합이 k보다 커지면 앞 원소를 제거해나가며 답을 찾자!

=> 이게 투 포인터의 개념

 

 

🚩 시행착오

• sum>k 일 때 제일 앞 원소를 제거하는데, 이 때 sum==k 가 될 수도 있다는 점을 간과함. 그래서 제거한 후 sum==k 이면 길이를 비교하고 answer을 업데이트하는 코드를 복붙함. (비효율적이지만..)
• 테스트 16, 25에서 실패함. 처음엔 size를 1,000,000으로 초기화했기 때문... sequence의 최대 길이가 1,000,000이므로 정답으로 1,000,000도 가능함. 따라서 반드시 정답보다 큰 수여야 하는 size는 1,000,000보다 커야 함.

 

 

💻 코드 (C++)

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;

    int sum=0; int start=0; int end=-1; int size=1000001;
    for(int i=0; i<sequence.size(); i++){
        sum += sequence[i];
        end = i;

        if(sum<k){
            continue;
        }else if(sum>k){
            while(sum>k){
                sum-=sequence[start];
                start++;
            }
            if(sum==k){
                if(end+1-start<size){
                    answer.clear();
                    answer.push_back(start);
                    answer.push_back(end);
                    size = end+1-start;
                }
            }
        }else{
            if(end+1-start<size){
                answer.clear();
                answer.push_back(start);
                answer.push_back(end);
                size = end+1-start;
            }
        }
    }

    return answer;
}