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

문제

 

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

프로그래머스

 

 

 

문제풀이

 

투 포인터를 이용해 문제를 풀었다.

sum에 left부터 right까지의 값을 더하면서 값이 k가 될 때 answer에 저장한 값과 비교하면서 값을 갱신한다.

sum이 k보다 작을 때는 sequence[right]의 값을 sum에 더하고,

sum이 k일 때는 answer에 저장된 부분 수열의 길이보다 현재 길이가 짧을 경우 갱신한다.

sum이 k보다 클 때는 sequence[left]의 값을 sum에서 뺀다.

 

만약 right가 오른쪽 끝까지 갔다면, left를 오른쪽으로 옮기면서 k와 같은 값이 되는지를 판별한다.

 

코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int>answer(2, 0);
    answer[1] = sequence.size() - 1;
    int left(0), right(0), sum(0);

    while (right < sequence.size()) {
        if (sum < k) {
            sum += sequence[right++];
            continue;
        }
        else if (sum == k) {
            if (answer[1] - answer[0] + 1 > right - 1 - left + 1) {
                answer[1] = right - 1;
                answer[0] = left;
            }
            sum -= sequence[left++];
        }
        else if (sum > k) {
            sum -= sequence[left++];
        }
    }

    while (left < sequence.size()) {
        sum -= sequence[left++];
        if (sum == k) {
            if (answer[1] - answer[0] + 1 > right - 1 - left + 1) {
                answer[1] = right - 1;
                answer[0] = left;
            }
        }
    }

    return answer;
}