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

문제

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

프로그래머스

오름차순으로 정렬된 수열의 합이 K인 최단 길이 부분 수열을 찾는 문제였다.

 

문제 풀이

처음에 완전탐색을 이용해 풀었다가 시간 초과가 났고, 중간에 중단 조건을 걸어 시간을 많이 줄였지만 그래도 시간 초과가 나서 다른 방법을 찾았다. 수열의 최대 길이가 100만이라 O(n^2) 방법이 아닌 O(n)으로 풀어야할 것 같아서 투포인터를 사용해 풀었다.

 

sum이 k보다 클 경우 l 값을 빼준 후 l을 이동시켜야 했는데 둘의 순서를 바꿔서 테케에서 2문제가 틀리는 일이 있었다. 그래도 금방 찾아내서 다행이었다. ㅎㅎ

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer(2);
    int i,j;
    int seSize = sequence.size();
    int length = seSize+1;
    int sum = sequence[0];
    int l=0,r=0;

    while(l<=r && r<seSize){
        //printf("l: %d r: %d sum: %d\n",l,r,sum);
        if(sum < k){ //숫자 더하기
            r++;
            sum += sequence[r];
        }
        else if(sum > k){ //앞의 숫자 빼기
            sum -= sequence[l];
            l++;
        }
        else { //같으면 길이 비교 후 갱신
            if(length > r-l+1){
                length = r-l+1;
                answer[0] = l;
                answer[1] = r;
            }
            r++;
            sum+=sequence[r];
        }
    }
    
    return answer;
}