[ BOJ / 투포인터 ] 차집합

1. 문제

---

 

1822번: 차집합

 

 

2. 소스코드

---

- 교집합을 구하는 문제와 해결방법이 동일하다.

2020/07/08 - [PS/구름] - [ 투포인터 ] 교집합 찾기

 

- 둘 다 정렬 후, 투포인터 알고리즘을 이용한다.

- 초기 세팅으로 A, B 두 배열을 오름차순으로 정렬한다. ( 1, 2, 3, 4 ..... )

1) A-B 연산을 한다고 하면, A의 배열 끝에 도달할때까지 알고리즘을 수행한다.

2) 포인터A와 포인터B을 0으로 초기화 한다. 포인터 A는 A배열의 첫 원소를, 포인터 B는 B배열의 첫 원소를 가리킨다.

3) 포인터A와 포인터B가 가리키는 값을 비교한다

3-1) 포인터B의 인덱스가 배열B를 초과했거나, 포인터A의 값이 더 작은 경우, 정답에 추가 및 포인터A를 +1 증가시킨다.

3-2) 포인터A의 값이 더 큰 경우, 포인터B를 + 1 증가시킨다.

3-3) 같은 경우 포인터A,B 둘 모두 +1증가시킨다.

 

소스코드

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

int n, m, ptrA, ptrB;
vector <int> setA, setB;
vector <int> ans;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
    setA.resize(n);
	for (int i = 0; i < n; ++i)
		cin >> setA[i];

	setB.resize(m);
	for (int i = 0; i < m; ++i)
		cin >> setB[i];
	
	ans.reserve(n);

	sort(setA.begin(), setA.end());
	sort(setB.begin(), setB.end());

	while (ptrA < n) {
		if (ptrB >= m or setA[ptrA] < setB[ptrB]) ans.push_back(setA[ptrA++]);
		else if (setA[ptrA] > setB[ptrB]) ptrB++;
		else ptrA++, ptrB++;
	}

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

	cout << ans.size() << '\n';
	for (int num : ans) cout << num << ' ';
 
	return 0;
}