[알고리즘] 투포인터(two pointers)

투포인터는 전혀 알지 못했는데 카카오 코딩테스트 문제를 풀다가 우연히 알게 되었습니다. 처음 봤을 때 2개의 변수값을 조금씩 움직여가는것이 매개변수 탐색과 비슷하다고 생각했습니다. 

 

투포인터는 1차원 배열에서 각각의 index를 가리키는 2개의 변수를 조작해가면서 문제를 해결하는 기법입니다. 투포인터를 백준문제를 보면서 설명하겠습니다.

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

문제는 1차원 배열에서 i번째에서 j번째까지의 합이 M이 되는 경우의 수를 구하는 문제입니다. 단순히 2중 for문을 사용하면 쉽게 구할 수 있지만 이 경우 시간복잡도는 O(N^2)입니다. 하지만 투포인터를 사용하면 O(N)만에 답을 구할 수 있습니다 !

 

먼저 2개의 변수 s,e 0를 초기화 하고 sum 변수를 선언합니다. sum은 s~e까지의 합을 의미합니다. 

만약 현재 sum값이 M보다 작으면 e번째 값을 넣고 e++합니다. 그리고 sum값이 M과 같거나 크다면 s값을 빼고 s--합니다. 만약 sum과 M이 같다면 개수를 세어줍니다. 이 과정을 e가 배열을 벗어나지 않을떄까지 반복하는 것입니다. 

 

1. sum < M 이면 sum에 arr[e]를 더하고 e++

2. sum >= 이면 sum에서 arr[s]를 빼고 s++, 만약 sum = M이면 count++

3. 1,2번 과정을 반복하다가 e가 배열의 크기와 같으면 종료한다.

 

#include <iostream>

using namespace std;

int main()
{

    int N, M;
    int arr[10001] = {0};

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    int s = 0, e = 0;

    int sum = 0;
    int count = 0;

    while (true)
    {

        if (sum >= M) 
        {
            if (sum == M)
            {
                count++;
            }

            sum -= arr[s]; // sum값이 M보다 크거나 같으면 s위치값을 빼주고 s++
            s++;
        }
        else if (e == N) // 끝에 도달하면 break
        {
            break;
        }
        else
        {
            sum += arr[e]; // sum값이 M보다 작으면 계속 e위치 값을 더해준다
            e++;
        }
    }
    cout << count << endl;
    return 0;
}