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

 이 문제는 투 포인터를 이용해서 풀었다. 일단 이 문제의 입력 배열의 최대 크기가 100만이므로 O(n) 시간 이하의 알고리즘을 사용해야 한다. 그래서 투 포인터를 떠올렸고, 왼쪽에서 두 포인터가 모두 시작하는 방향으로 구현하였다.

 

 

 정답으로 리턴해야하는 값이 부분 배열의 처음과 끝 인덱스인데, 끝 인덱스가 포함된 범위이므로 right++을 할 때 더 조심해야 한다. 그래서 right++을 하는 로직마다 size를 넘었는지 체크하는 부분을 집어넣었다. 또한 왼쪽에서 둘 다 시작하는 투 포인터는 반드시 두 포인터가 만났을 때는 right가 증가해야 두 포인터가 교차하여 발생하지 않게 된다.

 

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int left = 0;
    int right = 0;
    int acc = sequence[left];
    
    int answerLeft = -1;
    int answerRight = -1;
    int answerLength = 1000000001;
    
    while (right < sequence.size()) {
        if (left == right) {
            if (acc == k) {
                if (answerLength > right - left + 1) {
                    answerLength = right - left + 1;
                    answerLeft = left;
                    answerRight = right;
                }
                else if (answerLength == right - left + 1) {
                    answerLeft = min(answerLeft, left);
                    answerRight = min(answerRight, right);
                }
                
                if (right + 1 < sequence.size()) {
                    left++;
                    right++;
                    acc = sequence[right];
                }
                else {
                    break;
                }
            }
            else {
                right++;
                if (right < sequence.size()) {
                    acc += sequence[right];
                }
            }
        }
        else {
            if (acc < k) {
                right++;
                if (right < sequence.size()) {
                    acc += sequence[right];
                }
            }
            else if (acc > k) {
                acc -= sequence[left];
                left++;
            }
            else {
                if (answerLength > right - left + 1) {
                    answerLength = right - left + 1;
                    answerLeft = left;
                    answerRight = right;
                }
                else if (answerLength == right - left + 1) {
                    answerLeft = min(answerLeft, left);
                    answerRight = min(answerRight, right);
                }
                
                acc -= sequence[left];
                left++;
                right++;
                if (right < sequence.size()) {
                    acc += sequence[right];
                }
            }
        }
    }
    
    answer.push_back(answerLeft);
    answer.push_back(answerRight);
    
    return answer;
}