투포인트 알고리즘이란 말 그대로 두개의 포인터를 사용하는 알고리즘이다. 물론 두개 이상도 가능하다. 한가지 예로 들면 두개의 길이가 다른 배열이 있을 때, 이 배열들을 서로 비교하면서 무엇인가를 하고 싶을때 사용하면 효과적이다.
밑에 코드는 그냥 다음의 문제를 풀 때 투포인트 알고리즘을 사용하는 것을 보여주는 것이다.
n = 5, m = 4
2 7 10 5 3
3 17 5 10
위와 같은 무작위로 정렬된 서로다른 두 배열의 교집합을 구해보자.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define instructor
int main()
{
int n = 0, m=0,posA=0, posB=0;
scanf("%d",&n);
vector<int> a(n);
for(int i=0; i<n; i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
vector<int> b(m);
for(int i=0; i<m; i++){
scanf("%d",&b[i]);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
//먼저 두 배열을 초기화 하는 과정이다.
vector<int> answer;
// 이후 두개의 point인 posA와 posB에 따라 값을 넣어준다.
while(posA <= n && posB <=m){
if(a[posA]==b[posB]){
// 두 값이 같은 경우 우리가 찾는 교집합이기 때문에 이를 answer vector에다 넣고 각 point들을 한칸씩 이동시킨다.
answer.push_back(a[posA]);
posA++;
posB++;
}
/// 밑에 두 조건문은 point에 따른 원소에 값에 따라 point를 이동시키는 것
else if(a[posA]>b[posB]) posB++;
else posA++;
}
for(int i=0; i<answer.size(); i++) printf("%d\n",answer[i]);
return 0;
}
위의 정렬 방법의 시간복잡도는 sort() 함수가 퀵 솔트로 만들어 진것이므로 O(nlogn)이다. 그러나 이미 정렬된 배열일 경우 시간복잡도는 O(n)으로 매우 효율적인 알고리즘이다.