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

---

 

1. 투포인터를 사용한다. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라 하자.
2. sum(lo, hi) < k 이면 hi를 늘린다.
3. sum(lo, hi) > k 이면 lo를 늘린다.

 

1. 투포인터를 사용한다. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라 하자.

 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라고 두자. 수열이 비내림차순으로 정렬되어 있기 때문에 hi를 늘리면 무조건 sum(lo, hi)는 증가한다. 또한 모두 양수이므로 lo를 늘리면 무조건 sum(lo, hi)는 감소한다. 따라서 투포인터를 사용하여 O(N)에 해결할 수 있다. lo = 0, hi = 0인 경우부터 시작한다.

 

2. sum(lo, hi) < k 이면 hi를 늘린다.

 sum(lo, hi) < k이면 부분 수열의 합이 더 커져야 하므로, 수를 더 추가해야 한다. 즉, lo를 줄이거나 hi를 늘려야 하는데, lo를 줄인 경우는 이미 탐색하고 넘어왔다. lo를 0부터 점차 증가시키고 있기 때문에 lo가 현재보다 더 작아지는 경우는 이미 탐색한 경우에 해당한다. 따라서 hi를 늘려보기만 하면 된다.

 

3. sum(lo, hi) > k 이면 lo를 늘린다.

 sum(lo, hi) > k이면 부분 수열의 합이 더 작아져야 하므로, 수를 더 빼야 한다. 즉, lo를 늘리거나 hi를 줄여야 하는데, 마찬가지로 hi를 줄인 경우는 이미 탐색하고 넘어왔다. 따라서 lo를 늘려보기만 하면 된다.

---

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    int lo = 0, hi = 0, sum = sequence[0];
    
    while (lo <= hi && hi < sequence.size()) {
        if (sum == k) {
            if (answer.empty() || (answer[1] - answer[0] > hi - lo)) {
                answer = {lo, hi}; 
            }
        }
        
        if (sum < k) {  // k보다 작은 경우 더 추가해야 함
            hi++;
            sum += sequence[hi];
        }
        else {  // k보다 큰 경우 빼야 함
            sum -= sequence[lo];
            lo++;
        }
    }
    
    return answer;
}