[인프런 C++] 40. 교집합(투포인터 알고리즘)

🍧 문제

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

 

🍧 입력

첫 번째 줄에 집합 A의 크기 N이 주어진다.

두 번째 줄에 N개의 원소가 주어진다. 원소가 중복되지 않는다.

세 번째 줄에 집합 B의 크기 M이 주어진다.

네 번째 줄에 M개의 원소가 주어진다. 원소가 중복되지 않는다.

각 집합의 원소는 int형 변수의 크기를 넘지 않는다.

 

🍧 출력

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

 

🍧 1트 (강의 풀이)

이중 for문 사용 지양

a와 b배열을 정렬하고 비교해주어야 한다. 

비교해서 다르면 👉 작은 숫자가 있는 배열의 위치를 이동

비교해서 같으면 👉 두 배열의 위치를 모두 증가시킨다 & c배열에 넣어준다.

한 배열이 끝나면 while문 끝 & c배열 출력

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

int main(void){
	freopen("input.txt", "rt", stdin);
	int n, m, 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);
	for(int i = 0; i < m; ++i){
		cin >> b[i];
	}
	sort(b.begin(), b.end());
	
	vector<int> c(n+m);
	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;
}