[Programmers]#Level2_연속된 부분 수열의 합, 투 포인터

 

[Programmers 알고리즘, C++]#Level 2_연속된 부분 수열의 합

 

Programmers 알고리즘 문제 풀이, Level 2_연속된 부분 수열의 합

투 포인터 알고리즘을 활용해 부분 수열의 합을 구하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

1. 투 포인터 알고리즘

1. 시작점을 가리키는 포인터와 도착점을 가리키는 포인터 두 개를 선언합니다.
2. 두 포인터를 모두 수열의 0번째 원소를 가리키도록 초기화합니다.
3. 현재 부분 수열의 합이 목표 값보다 작다면, 도착점 포인터를 오른쪽으로 한칸 이동시키고
   그 값을 현재 부분수열의 합에 추가합니다.
4. 반대로, 현재 부분 수열의 합이 목표 값보다 크다면, 시작점 포인터를 오른쪽으로 한 칸 이동시키고,
   이전에 가리키던 값읠 현재 부분 수열의 합에서 뺍니다.
5. 목표 값을 찾을 때까지 위 과정을 반복합니다.

 

Details

 

• 투 포인터 알고리즘은 배열 혹은 리스트와 같은 선형 자료구조에서 두 개의 지점을 기억하며 움직이는 알고리즘입니다. 주로, 정렬된 상태의 선형 자료구조의 두 지점을 정해 해당 구간에 존재하는 원소들의 합, 즉 부분 수열의 합을 찾는 데 사용됩니다.
• 정렬되지 않은 수열은 map 컨테이너를 활용합니다.
• 문제는 정렬된 배열을 제공하며, 목표 값을 갖는 그 크기가 최소인 부분수열을 찾고 있습니다. 따라서, 목푯 값과 같은 합을 갖는 부분수열의 길이를 계산하고, 최소 길이를 갱신하며 투 포인터 알고리즘을 진행합니다!

 

#3. 코드

 

#include <string>
#include <vector>
#include <climits>

using namespace std;

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

    int left = 0;
    int right = 0;
    int sum = 0;
    int min_length = INT_MAX;
    
    answer.resize(2, -1);
    
    while(right <= sequence.size() && left < sequence.size())
    {
        if(sum >= k || right == sequence.size())
        {
            if(sum == k && right-left+1 < min_length)
            {
                min_length = right-left+1;
                answer[0] = left;
                answer[1] = right-1;
            }
            sum -= sequence[left++];
        }
        else
        {
            sum+= sequence[right++];
        }
    }
    
    return answer;
    
}