[Algorithm] Two-Pointer (투 포인터 알고리즘)

풀이

1. 두 집합의 교집합을 찾기 위한 알고리즘

2. 이중 for loop를 사용할 때는 O(N^2) 이지만, 투 포인터 알고리즘으로 O(N)으로 해결 가능

3. 각 집합을 오름차순 정렬하고, 두 포인터 변수가 가르키는 값이 다르다면 작은 쪽의 포인터를 증가, 같다면 모두 증가 시키는 방법으로 교집합을 찾는다

예시)

a: {1 3 4 6}

b: {4 5 6 7}

오름차순 정렬된 두 집합이 존재할 때 a 집합의 포인터를 p1 = 0, b 집합의 포인터를 p2=0 라 하자.

a[p1] < b[p2] 이기 때문에 a 집합에서 더 큰 원소를 가져와서 비교해야 한다. 따라서 p1++ 한다.

계속 진행해서 p1 = 2 일 때 a[p1] == b[p2] 가 되고, 모든 포인터를 하나씩 증가시키면서 교집합을 업데이트 하면 된다.

반대의 경우 p2++를 해주면 된다.

한쪽의 포인터가 끝에 도착하면 비교가 끝나기 때문에 알고리즘은 O(N)으로 교집합을 찾아낼 수 있다.

 

리뷰

기존의 for loop 방식에서 포인터 변수를 쓰는 방식에 익숙해 지는 것이 문제 해결에 많은 도움이 될 것 같다.

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;
/*
2중 for loop 보다 두개의 포인트 변수를 사용하면 입력이 커져도 1초 이내 해결 가능
투포인트 알고리즘은 오름차순 정렬 되어 있어야 함
두 숫자 중 작은 쪽의 포인터를 증가시킴
두 숫자가 같다면 포인트 두개를 모두 증가 시킴
*/

int main(){
	freopen("input.txt", "rt", stdin);
	int n, m, i, p1=0, p2=0, p3=0;
	scanf("%d", &n);
	vector<int> a(n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	
	scanf("%d", &m);
	vector<int> b(m), c(m);
	for(i=0; i<m; i++){
		scanf("%d", &b[i]);
	}

    // Two-Pointer Algorithm
    sort(a.begin(), a.end()); 
	sort(b.begin(), b.end());
	
	while(p1<n && p2<m){
        // 교집합 -> 포인터 두개 모두 증가
		if(a[p1]==b[p2]){
			c[p3++]=a[p1++];
			p2++;
		}
        // 작은 쪽의 포인터 증가 -> 오름차순 정렬 했으므로 더 큰 수를 비교해야 함
		else if(a[p1]<b[p2]){
			p1++;
		}
		else p2++;
	}
    // Output
	for(i=0; i<p3; i++){
		printf("%d ", c[i]);
	}
	return 0;
}