Two pointers

Two pointers

    - 배열 A에서 2개의 포인터를 이용해서 문제를 해결하는 알고리즘

 

 

 

동작

    - 포인터를 어떻게 움직이느냐에 따라 조금 다릅니다. 여기서는 시작점에서 2개의 포인터를 오른쪽으로 이동시키는 알고리즘을 설명하겠습니다.

    1. 2개의 포인터(left, right)는 배열의 첫 부분을 가리킨다.

    2. 두 포인터가 가리키는 값의 합이 목표치 X보다 작으면, right 포인터를 오른쪽으로 한 칸 옮깁니다.

    3. 두 포인터가 가리키는 값의 합이 목표치 X보다 크면, left 포인터를 오른쪽으로 한 칸 옮깁니다.

    4. right 포인터가 배열의 끝에 갈 때까지 또는 문제의 특정 목표에 도달하면 동작을 끝냅니다.

 

 

    - two pointers에 대한 좋은 강의가 있어서 참고했습니다.

 

 

 

 

 구현

    - www.acmicpc.net/problem/1806

1806번: 부분합

    - 위 문제를 예시로 구현하겠습니다.

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n, s;
 
int arr[100001];
 
int main(void){
    
    cin >> n >> s;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    int left=0, right=0;
    int sum = arr[0];
    int answer = 987654321;
    
    while(left<=right && right<n){
        if(sum < s){
            sum += arr[++right];
        } else if(sum >= s){
            answer = min(answer, right-left+1);
            sum -= arr[left++];
        }
    }
    
    if(answer == 987654321) cout << 0 << endl;
    else cout << answer << endl;
    
 
 
}
 

 

특징

    - 시간 복잡도 : O(n).  right 포인터가 배열의 끝에 도달하는 경우

        * 최악의 경우 : O(n). left와 right 두 개의 포인터가 배열의 끝까지 도달하는 경우

 

 

 

참고

    - video

    - Two pointers