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

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

1822번: 차집합

이분 탐색을 이용하면 시간복잡도 O(N * logN)으로 해결할 수 있다. 다만 주의할 점은 a 집합에서 교집합 원소를 제거하는 방식으로 문제를 접근하면 원소의 재배치 과정 때문에 TLE이 발생할 수 있다. 그러므로, 이분 탐색을 통해 찾을 수 없는 원소인 경우에 새로운 벡터에 값을 넣는 방식으로 해결하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m), res;
    
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i  < m; i++) {
        cin >> b[i];
    }
    sort(b.begin(), b.end());
    
    for(int i = 0; i < n; i++) {
        int flag = binary_search(b.begin(), b.end(), a[i]);
        if(flag == 0) res.push_back(a[i]);
    }
    
    sort(res.begin(), res.end());
    
    cout << res.size() << "\n";
    for(int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
}