[백준 1822번] 차집합 (C++)

문제링크 : https://www.acmicpc.net/problem/1822

1822번: 차집합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int na, nb, a[500001], b[500001];
map<int, int>m;
vector<int>v;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> na >> nb;

    for(int i=0; i<na; i++) cin >> a[i];
    for(int i=0; i<nb; i++) 
    {
        cin >> b[i];
        m[b[i]]++; //집합 B 카운팅
    }

    for(int i=0; i<na; i++) 
    {
        if(m[a[i]]) continue; //이미 B에서 카운팅되어있으면 스킵
        v.push_back(a[i]);
    }

    sort(v.begin(), v.end()); //증가하는 순서로 출력

    cout << v.size() << "\n";

    for(int i=0; i<v.size(); i++) cout << v[i] << " ";

    return 0;
}

 

먼저 B에 대한 내용을 입력받고, map을 이용하여 카운팅해준다.

만약 A에 대해 map을 이용하여 해당 Key에 대한 Value가 있다면 이는 B에서 이미 카운팅했다는 의미이므로 패스한다.

Value가 없다면 새로운 값이므로 따로 벡터에 저장한다.

 

문제에 주어진 조건에 따라 벡터를 정렬하고, 크기와 내용을 출력해주면 된다.