40. 교집합(투포인트 알고리즘)

문제설명

두 집합 A, B가 주어지면 두 집합의 교집합을 출력하는 프로그램을 작성하세요

입력설명

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
각 집합의 원소는 int형 변수의 크기를 넘지 않습니다.

출력설명

두 집합의 교집합을 오름차순 정렬하여 출력합니다.

내 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n, m;
	cin >> n;
	vector<int> v(n);
	vector<int> v2(n);
	vector<int> v3;
	for (int i = 0; i < n; i++)
		cin >> v[i];
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> v2[i];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (v[i] == v2[j])
				v3.push_back(v[i]);
		}
	}
	sort(v3.begin(), v3.end());
	for (int i = 0; i < v3.size(); i++)
		cout << v3[i]<<" ";
}

투 포인터 알고리즘

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n, m, p1 = 0, p2 = 0, p3 = 0;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	cin >> m;
	vector<int> v2(m);
	vector<int> v3(n + m);
	for (int i = 0; i < m; i++)
		cin >> v2[i];
	
	sort(v.begin(), v.end());
	sort(v2.begin(), v2.end());

	while (p1 < n && p2 < m)
	{
		if (v[p1] == v2[p2])
		{
			v3[p3++] = v[p1++];
			p2++;
		}
		else if (v[p1] < v2[p2])
			p1++;
		else
			p2++;
	}
	for (int i = 0; i < p3; i++)
		cout << v3[i]<<" ";
}