백준 2003번: 수들의 합 2 (C++), 투 포인터

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

종종 유용하게 사용되는 테그닉, 투 포인터(Two Pointers)에 대해 알아보자.

 

예를 들어, 배열 A가 존재한다고 했을 때, 링크를 걸어둔 문제처럼 A[i] + A[i+1] + … + A[j-1] + A[j] 중 M이 되는 경우의 수를 구하라 했을 때, 어떻게 할 것인가?

 

구간 합이라 세그먼트 트리를 이용해야 할 거 같지만 세그먼트 트리를 구성한 다음 쿼리는 어떻게 짤 것인지 생각해보면 막막하기만 하다. 이럴 때, 세그먼트 트리를 이용하지도 않고, 투 포인터 알고리즘을 사용하면 된다.

 

투 포인터는 말 그대로 포인터를 두 개 사용하여 포인터가 가리키는 시작점과 끝점에서 일어나는 일, 혹은 시작점과 끝 점 사이에서 일어나는 일을 처리하기에 편한 알고리즘이다.

 

Time Complexity는 right가 누적으로 N번까지 가야 끝이 나기 때문에 O(N)이다. left가 right와 같이 끝까지 가더라도 빅오 표기법에 의해 시간 복잡도는 O(N)이 된다.

 

두 포인터를 가리키는 말은 [start, end], [left, right]처럼 본인이 편한 대로 사용하는 것이 좋다.

이 포스팅에서는 left와 right로 하겠다.

 

[동작 원리]

• left, right 둘 다 똑같은 시작점에서 시작한다.
• 만족하는 m이 되거나 m보다 커지기 전까지 right를 움직인다.
• right를 움직이면서 해당 right 인덱스의 배열의 값들을 더해나간다.
• 만약 right를 움직이는 조건의 반대가 되었다면
• left가 가리키는 인덱스의 배열 값을 빼고, left를 움직이게 한다.
• right가 배열의 크기를 넘어서는 순간, 알고리즘을 종료시킨다.

 

이렇게 말보다 코드를 보는 것이 더 효율적일 수도 있다.

[AC 코드]

#include <iostream>
#include <vector>
#define left l
#define right r
using namespace std;

vector<long> v;
int n;
long m;
long sum = 0;
int left = 0;
int right = 0;
int answer = 0;

void twoPointers(){
    while(true){
        if(sum >= m){
            sum -= v[left];
            left++;
        }
        else{
            if(right == n) break;
            sum += v[right];
            right++;
        }
        
        if(sum == m) answer++;
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        v.push_back(a);
    }
    
    twoPointers();
    
    cout << answer;
    return 0;
}