[강의] 투포인트 알고리즘

투포인트 알고리즘

• 이중 포문으로 O(N^2)이 아닌 1초안에 답이 나오게 하기 위한 알고리즘

 

 

 

예제)

풀이

• STEP1)A배열, B배열, C배열(교집합배열)을 만든다.
• STEP2)A배열 0번째, B배열 0번째 비교해서  (A[0] < B[0])이면 A 배열의 포인터를 +1 만큼 증가 시킨다. 즉 더 작은 값의 배열을 +1 증가 시킨다.
• STEP2,3)A[1] == B[0] 이면 그 값을 C[0]에 넣고 C[cnt++]해준다. 또한, A배열, B배열 포인터를 +1 만큼 증가시킨다.
• STEP4)누군가 하나의 배열이 끝나면 종료.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main()
{
	int n, m, i, p1 = 0, p2 = 0, p3 = 0;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a.begin(), a.end());
	cin >> m;
	vector<int> b(m), c(n + m);

	for (int i = 0; i <m; i++)
	{
		cin >> b[i];
	}

	sort(b.begin(), b.end());

	//2point
	while (p1 < n && p2 < m)
	{
		if (a[p1] == b[p2])
		{
			c[p3++] = a[p1++];
			p2++;
		}
		else if (a[p1] < b[p2])
			p1++;
		else
			p2++;

	}
	for (int i = 0; i < p3; i++)
		cout << c[i] << " " ;
	return 0;
}