[BOJ] 1822번 차집합 (C++)

https://www.acmicpc.net/problem/1822

1822번: 차집합

 

#include <iostream>
#include <set>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m, k;
	cin >> n >> m;
	
	set<int> s;
	
	for(int i = 0; i < n; i++){
		cin >> k;
		s.insert(k);
	}
	for(int j = 0; j < m; j++){
		cin >> k;
		s.erase(k);
	}
	
	cout << s.size() << endl;
	for(auto it = s.begin(); it != s.end(); it++){
		cout << *it << ' ';
	}
	return 0;
}

 

vector을 사용하여 풀었을 때 계속 시간 초과가 나왔다. vector의 push_back은 속도가 느리다.

따라서 연관 컨테이너로 바꿔서 풀거나 vector을 사용할 경우 reserve를 사용해야 한다. (링크 참조)

https://thuthi.tistory.com/entry/vector-pushback%EC%9D%80-%EB%8A%90%EB%A6%AC%EB%8B%A4-reserve