투포인터 알고리즘

투포인터 알고리즘

두 개의 일차원 배열이 있고, 그 배열을 서로 비교해서 새로운 배열을 만든다고 합시다.

각 수를 하나하나 비교해서 배열을 만들면, 두 배열의 크기가 N, M이라고 할 때 시간 복잡도는 N*M이 됩니다.

이러한 큰 시간 복잡도를 줄이기 위해, 각 배열에 하나씩 두 개의 포인터를 지정합니다.

이 포인터들을 상황에 맞게 움직이면서 작은 시간 복잡도로 문제를 해결하는 것이 투포인터 알고리즘입니다.

문제

대표 문제를 살펴봅시다.

문제 : BOJ_1822번 차집합

두 개의 1차원 배열이 있고, 배열의 최대 크기는 500,000입니다.

이때 두 배열의 차집합을 만드는 것이 문제입니다.

서로의 배열 값을 단순하게 하나하나 비교하면 시간 복잡도가 커집니다.

이때 투포인터를 활용해 문제를 해결합니다.

해결 방법

일단 두 배열이 크기순으로 정렬되어 있지 않으므로 각각 배열을 오름차순으로 정렬해 줍니다.

그리고 배열 1의 포인터 ptr1, 배열 2의 포인터 ptr2를 선언하고 그 값은 배열의 첫 번째 인덱스로 할당합니다.

각 포인터의 값을 인덱스로 하여 서로의 배열 값을 비교해 줍니다.

그리고 세 가지 경우를 비교합니다.

1. 배열 1과 배열 2의 값이 서로 같다면, 서로의 포인터 값을 올려주고 넘어갑니다.
2. 배열 1의 값이 배열 2의 값보다 크다면, 차집합의 기준은 배열 1이므로 배열 1의 값을 결과 배열에 넣어주고 배열 1의 포인터 값을 올려줍니다.
3. 배열 2의 값이 배열 1의 값보다 크다면, 배열 2의 포인터 값을 올려주고 넘어갑니다.
4. 이런 투포인터 방식으로 비교가 가능한 이유는 두 배열이 정렬되어 있기 때문입니다.

풀이 소스

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    int nA, nB;
    cin >> nA >> nB;
    vector<int> v1(nA);
    vector<int> v2(nB);
    for (int i = 0; i < nA; i++) cin >> v1[i];
    sort(v1.begin(), v1.end());
    for (int i = 0; i < nB; i++) cin >> v2[i];
    sort(v2.begin(), v2.end());

    int ptr1, ptr2;
    ptr1 = ptr2 = 0;


    vector<int> result;
    while (ptr1 < nA && ptr2 < nB) {
        if (v1[ptr1] == v2[ptr2]) {
            ptr1++;
            ptr2++;
        }
        else if (v1[ptr1] > v2[ptr2]) ptr2++;
        else {
            result.push_back(v1[ptr1]);
            ptr1++;
        }
    }

    while (ptr1 < nA) {
        result.push_back(v1[ptr1]);
        ptr1++;
    }
        cout << result.size() << '\n';
        for (int i : result) {
            cout << i << ' ';
        }
        cout << '\n';


    return 0;
}

• vector로 배열 1, 배열 2를 동적할당하고, 결과 배열은 값이 들어올 때마다 push_back 해주었습니다.
• sort 함수를 이용해 배열 1과 배열 2를 오름차순 순으로 정렬했습니다.

시간 복잡도

기존에 단순한 2중 for 문의 경우엔 최악의 경우엔 N*M이 나옵니다.

투포인터 알고리즘은 포인터를 하나하나 증가시키며 비교하므로 N+M만에 해결이 가능합니다.