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

개요

문제를 처음 읽었을 때, 문제를 이해하는 것은 어렵지 않았다. 굉장히 간단한 문제였다.

그러나, 문제를 이해한 후에, 어떤 방식으로 접근해야 하는지가 어려웠다.

 

sequence의 길이 <= 100만이기 때문에 O(N^2) 풀이는 불가능했다.

O(N) 또는 O(NlogN)의 풀이를 생각해야만 했다.

 

또한, 문제 조건에서 sequence가 비내림차순(= 단조증가)인 것도 잘 봐두자.

 

고민 끝에, O(N)의 풀이로 해결할 수 있는 '투포인터' 방식을 이용하기로 했다.

(사실, 투포인터 방식을 사용하기로 결정한 후에도 정답을 도출하기까지 1시간이 넘게 걸렸다...)

정답 코드

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

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    int start = -1, end = -1, sum = 0;
    int seqlen = sequence.size();
    while(start <= end && end < seqlen){
        if (sum < k){
            end++;
            sum += sequence[end];
        }
        else if (sum > k){
            start++;
            sum -= sequence[start];
        }
        else if (sum == k){
            if (answer.size() == 0)
                answer = {start + 1, end};
            else if (end - (start + 1) < answer[1] - answer[0])
                answer = {start + 1, end};
            
            start++;
            sum -= sequence[start];
        }
    }
    return answer;
}

사실 첫 정답은 다른 코드로 맞췄지만, 좀 더 간결하게 정리하여 새로운 코드를 작성했다.

 

이 코드의 핵심은 '투포인터'를 이용했다는 것이다.

투포인터 방식에는 초기에 start, end를 -1로 설정하기도 하고, 0으로 설정하기도 한다.

나는 start, end를 -1로 설정하는 방식을 사용하기로 했다.

 

그리고 또 중요한 점은, start와 end가 나타내는 범위가 (start, end] 임에 주의하자!!

즉, start 초과 (start는 포함X), end 이하인 범위인 것이다.

예를 들어, start = 1, end = 5이면, 우리는 인덱스 2부터 5까지를 보고 있는 것으로 생각해야 한다.

 

투포인터의 while문 조건에는 start <= end && end < (배열 길이)가 들어가면 된다.

 

그리고, sum이 k보다 큰 경우, 작은 경우, 같은 경우 3가지의 case로 나누어 if문을 작성하면 된다.

 

Case1) sum < k

sum이 k보다 작은 경우에는 end를 늘려준 후에 sum에 sequence[end]를 더한다.

(sum 값을 증가시켜준 후에 k와 같아지는지 다시 확인하기 위한 것이다.)

 

Case2) sum > k

sum이 k보다 큰 경우에는 start를 늘려준 후에 sum에서 sequence[start]를 뺀다.

(sum 값을 감소시켜준 후에 k와 같아지는지 다시 확인하기 위한 것이다.)

 

Case3) sum == k

sum이 k와 같은 경우에는 answer에 시작 index와 끝 index를 넣어주어야 한다.

 

answer가 비어 있는 경우, 즉 answer의 size가 0인 경우에는 일단 바로 시작 index와 끝 index를 넣어주면 된다.

주의할 점은, 우리가 보고 있는 범위는 (start, end], 즉 [start + 1, end]이므로 {start + 1, end}를 넣어주어야 한다.

 

그리고, 이후에 sum이 k인 경우가 다시 나온다면 현재 시작 index, 끝 index를 이전에 answer에 저장된 시작 index, 끝 index와 비교해주어야 한다.

문제 조건에서, sum이 k인 경우가 여러 개인 경우, 길이가 짧은 것을 선택한다고 했다.

(그리고, 길이마저 같다면 더 앞에 나온 것을 선택하지만, 사실 앞에서부터 탐색했기 때문에 이 조건은 크게 고려하지 않아도 된다.)

그래서 end - (start + 1)이 answer[1] - answer[0]보다 작은 경우에 기존 answer의 값을 {start + 1, end}로 바꿔준다.

 

그리고, 마지막으로 sum이 k인 경우에도 start를 늘려준 후에 sum에서 sequence[start]를 뺀다.

(sum 값을 감소시켜준 후에 k와 같아지는지 다시 확인하기 위한 것이다.)

깨달은 점

1. 투포인터의 시간 복잡도는 O(N)이다.

2. 투포인터에서 start = -1, end = -1로 설정하되, 우리가 보고 있는 범위는 start + 1부터 end까지이다. (다르게 접근하기도 하지만, 나는 이렇게 접근하기로 했다.)