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<< " ";
}