[Programmers] 연속된 부분 수열의 합(Lv.2)

풀이 소요시간 : 60분 초과(실패)

처음으로 풀어본 투 포인터 유형의 문제다. 프로그래머스는 문제풀이 유형을 보여주지 않기 때문에 실전과 비슷한 느낌이 나는 것 같아 좋다. BOJ 플랫폼에서 이런 타입의 문제를 푸는 경우, 대부분 백트래킹 방식을 사용했기 때문에 백트래킹을 사용해 구현하였고, 시간초과로 실패했다.

한시간 정도 리팩토링을 해보다가 뭔가 접근 자체가 잘못되었다는 생각을 했고, 풀이를 참고했다. 투 포인터라는 유형의 문제였다.

투 포인터(Two Pointer)

시작 인덱스 st 와 마지막 인덱스 en 이 필요하다.

st 와 en 값을 이동시키며 범위의 값들로 특정 연산을 수행 가능하며, O(N) 의 아주 빠른 시간복잡도를 가지는 알고리즘이다.

이번 문제에서는 누적합 == K 가 되는 연속된 부분 수열의 st 와 en 값을 필요로 했고, 수열의 길이를 갱신하며 최소 길이 수열의 st 와 en 을 구해 반환해야했다.

전체 코드

참고로 마지막 인덱스 en 의 섬세한 처리가 굉장히 중요한 유형이다. 기억해두자.

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#define INF 1000000001
using namespace std;


int K;
int N; 
int Map[1000000];


vector<int> solution(vector<int> sequence, int k) {
    
    K = k;
    N = sequence.size();
    
    for(int i = 0; i < sequence.size(); i++) {
        Map[i] = sequence[i];
    }
    
    int Min = INF;
    pair<int, int> result;
    
    int Total = Map[0];
    int en = 0;
    for(int st = 0; st < N; st++) {
        
        while(en < N && Total < K) {
            //en = N - 1 의 경우
            en++;
            //en = N
            if(en != N) Total += Map[en];
        }
        if(en == N) break;
        
        if(Total == K) {
        
            int Gap = en - st + 1;
            
            if(Gap < Min) {
                Min = Gap;
                result = {st, en};
            }
            else if(Gap == Min && st < result.first) {
                result = {st, en};
            }
        
        }
        
        Total -= Map[st];
    }
    
    return {result.first, result.second};
    
}