(C++) - 백준(BOJ) 1822번 : 차집합 답

www.acmicpc.net/problem/1822

1822번: 차집합

 

map, vector 자료구조를 이용해 간단히 풀 수 있었던 문제였습니다.

 

풀이방법

 1. b의 원소를 key, 해당 원소의 빈도 수를 value로 한 map 자료구조를 만들어 저장합니다.

 2. a의 원소들중 map(b의 원소-key, 그 원소가 나온 빈도수-value)에 없는 원소들을 vector 자료구조에 저장합니다.

 3. 저장된 vector를 정렬 후 적절히 출력합니다.

Code

#include <bits/stdc++.h>
using namespace std;
int a[500001], b[500001], aSize, bSize;
map <int,int> m;
vector <int> notInB;

int main(){
    cin >> aSize >> bSize;
    for(int i = 0; i < aSize; i++) cin >> a[i];
    for(int i = 0; i < bSize; i++) cin >> b[i];

    for(int i = 0; i < bSize; i++) m[b[i]]++;
    for(int i = 0; i < aSize; i++){
        if(!m[a[i]]) notInB.push_back(a[i]);
    }

    sort(notInB.begin(),notInB.end());
    cout << notInB.size() <<'\n';
    for(auto p : notInB) cout << p << ' ';
}