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

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

프로그래머스

 

<알고리즘 분류>

   - 투 포인터 (Two Pointer)

   - 부분합 (Partial Sum)

   - 누적합 (Prefix Sum)

 

<풀이> 

  1. 주어진 sequence의 이후 덧셈(for문 활용 - 시간복잡도 O(n) 증가)를 줄여주기 위해, 처음부터 누적합의 형식으로 sequence를 저장한다. 

  2. 배열의 길이가 1,000,000이기 때문에, 모든 부분합을 계산하게 되면(O(n^2)) 시간초과가 발생한다. 따라서 투 포인터(Two Pointer) 아이디어를 떠올린다. (O(n) 으로 해결이 가능하다!)

 

<코드>

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

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    
    vector <pair <int, int>> p1; // 조건을 만족하는 값을 저장.
    int p_left= 0;
    int p_right = 0; //투 포인터
    
    for (int i=1; i<sequence.size(); i++){
        sequence[i] += sequence[i-1]; 
    }
    
    while (p_left <= p_right && p_right < sequence.size()){
        int pSum;
        
        if (p_left == 0) pSum = sequence[p_right];
        else  pSum = sequence[p_right] - sequence[p_left - 1];
        
        if (pSum == k){
            p1.push_back({p_left, p_right});
            p_left++;
            p_right++;
        }
        else if (pSum > k){
            p_left++;
        }
        else p_right++;
        
    }
    pair <int, int> minresult = {0, 1000000};
    
    for(int i=0; i<p1.size(); i++){
        if (p1[i].second-p1[i].first < minresult.second-minresult.first){
            minresult.first = p1[i].first;
            minresult.second = p1[i].second;
        }
        
    }

    return {minresult.first, minresult.second};
}