투포인터 알고리즘
두 개의 일차원 배열이 있고, 그 배열을 서로 비교해서 새로운 배열을 만든다고 합시다.
각 수를 하나하나 비교해서 배열을 만들면, 두 배열의 크기가 N, M이라고 할 때 시간 복잡도는 N*M
이 됩니다.
이러한 큰 시간 복잡도를 줄이기 위해, 각 배열에 하나씩 두 개의 포인터를 지정합니다.
이 포인터들을 상황에 맞게 움직이면서 작은 시간 복잡도로 문제를 해결하는 것이 투포인터 알고리즘입니다.
문제
대표 문제를 살펴봅시다.
문제 : BOJ_1822번 차집합
두 개의 1차원 배열이 있고, 배열의 최대 크기는 500,000입니다.
이때 두 배열의 차집합을 만드는 것이 문제입니다.
서로의 배열 값을 단순하게 하나하나 비교하면 시간 복잡도가 커집니다.
이때 투포인터를 활용해 문제를 해결합니다.
해결 방법
일단 두 배열이 크기순으로 정렬되어 있지 않으므로 각각 배열을 오름차순으로 정렬해 줍니다.
그리고 배열 1의 포인터 ptr1, 배열 2의 포인터 ptr2를 선언하고 그 값은 배열의 첫 번째 인덱스로 할당합니다.
각 포인터의 값을 인덱스로 하여 서로의 배열 값을 비교해 줍니다.
그리고 세 가지 경우를 비교합니다.
- 배열 1과 배열 2의 값이 서로 같다면, 서로의 포인터 값을 올려주고 넘어갑니다.
- 배열 1의 값이 배열 2의 값보다 크다면, 차집합의 기준은 배열 1이므로 배열 1의 값을 결과 배열에 넣어주고 배열 1의 포인터 값을 올려줍니다.
- 배열 2의 값이 배열 1의 값보다 크다면, 배열 2의 포인터 값을 올려주고 넘어갑니다.
- 이런 투포인터 방식으로 비교가 가능한 이유는 두 배열이 정렬되어 있기 때문입니다.
풀이 소스
#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
만에 해결이 가능합니다.
PREVIOUS[BOJ] 동전 2(2294)