[BOJ / C++] 차집합 (이분탐색)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

    int na, nb;
    cin >> na >> nb;

    vector<int> a(na);
    for (int i = 0; i < na; i++) {
        cin >> a[i];
    }
    
    vector<int> b(nb);
    for (int i = 0; i <  nb; i++) {
        cin >> b[i];
    }
    sort(b.begin(), b.end());

    vector<int> ans;
    for (int target: a) {
        if (!binary_search(b.begin(), b.end(), target)) {
            ans.push_back(target);
        }
    }
    sort(ans.begin(), ans.end());

    cout << ans.size() << '\n';
    for (int i: ans) {
        cout << i << ' ';
    }
}

 

 

2. 시간복잡도

na, nb가 최대 500,000이므로 각각 선형탐색해서 O(n^2)이 걸리면 시간초과가 된다. 따라서 정렬과 이분탐색을 통해 각각 O(nlgn)으로 시간복잡도를 낮춰야한다. nlgn = 5*10^5 * 20 < 10^8 이므로 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

이분탐색을 통해 시간복잡도를 O(nlgn)으로 낮추는 것이 키 포인트이다. 마지막에 구체적인 원소를 출력할 때도 증가하는 순으로 출력해줘야하는 것에 주의한다.