BOJ
[ BOJ / C++ ] 1822번 : 차집합
J_3s
2025. 4. 13. 17:15
[ BOJ ] 1822번 : 차집합
문제 : https://www.acmicpc.net/problem/1822
[ 문제 ]
몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.
[ 입력 ]
첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.
[ 출력 ]
첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.
[ 문제 접근 및 풀이 ]
Set에 A의 원소들을 모두 넣은 후
B에 있는 원소를 입력 받은 후 집합 A에 있는 지 확인하고 있는 경우 빼준다.
그 후 A에 있는 집합을 출력한다.
[ 소스 코드 ]
#include<bits/stdc++.h>
using namespace std;
int N,M,a,b;
set<int> A;
void Q_1822();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Q_1822();
}
void Q_1822(){
cin >> N >> M;
for(int i=0;i<N;i++){
cin >> a;
A.insert(a);
}
for(int i=0;i<M;i++){
cin >> b;
auto x=A.find(b);
if(x!=A.end()) A.erase(x);
}
cout << A.size()<<"\n";
for(auto x:A) cout << x<< " ";
}