프로그래머스 연속된 부분 수열의 합 문제 바로가기

Bruteforce

Simple is best라는 생각에 바로 bruteforce로 풀어보았다. 결과는… 시간초과 시간 복잡도가 $ O(n^{2}) $ 이기에 n이 조금만 커져도 기하급수적으로 증가한다.

#include <string>
#include <vector>
#include <numeric>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> setting(k, 1);
    vector<int> answer;
    for (int start=0; start<sequence.size(); start++){
        vector<int> temp;
        int i=start;
        while (reduce(temp.begin(), temp.end()) < k){
            temp.push_back(sequence[i]);
            if (reduce(temp.begin(), temp.end()) == k){
                if (setting.size() > temp.size()){
                    setting = temp;
                    answer = {start, i};
                }
            }
            i++;
        }
    }
    return answer;
}
  • 테스트 1~5 통과
  • 테스트 6 이후 → 시간 초과

Two Pointer

어떻게하면 불필요한 연산을 줄일 수 있을까 고민했다. 사실 스스로 그 답을 찾아내진 못했고, Two Pointer이라는 힌트를 얻었다. Two Pointer는 starting 위치에 따라서 연산을 새로 시작하지 않고 기존의 계산 결과를 활용한다. 따라서 bruteforce에 비해서 현격히 적은 시간을 소요로 한다. 시간 복잡도: $ O(n) $

내 풀이

#include <string>
#include <vector>
#include <numeric>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    int min_length = 1000001;
    int end = 0;
    int interval_sum=0;
    
    for (int start=0; start<sequence.size(); start++){    
        // end 하나씩 이동시키기
        while (interval_sum < k && end < sequence.size()){
            interval_sum += sequence[end];
            end++;
        }
        // 부분합이 k와 같을 경우
        if (interval_sum == k){
            if (end-start < min_length){
                answer = {start, end-1};
                min_length = end-start;
            }
        }
        interval_sum -= sequence[start];
        
    }
    return answer;
}

고수의 풀이

역시 깔끔하다… 나의 경우 min_length을 최댓값인 1000001로 잡고 풀어내었는데, 고수의 풀이의 경우 answer의 앞뒤 항목을 현재 end, start와 바로 비교해서 결정했다.

#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k)
{
    vector<int> answer;

    int srt=0, end=0, sum=0;

    for(int i=0; i<sequence.size(); i++)
    {
        end=i;
        sum+=sequence[end];

        while(sum>k)
            sum-=sequence[srt++];

        if(sum==k)
            if(answer.empty() || end-srt < answer[1]-answer[0])
                answer={srt, end};
    }

    return answer;
}

출처

References