1822 차집합

문제 링크

• 나의 풀이

처음에는 유니온 파인드를 이용해 풀려고 했지만 문제의 조건에서 원소의 값이 2,147,483,647까지 될 수 있음을 알고 포기해야만 했다. (배열을 2,147,483,647까지 만들어야 한다) B를 정렬한 뒤 A의 값을 순회하며 이분탐색을 이용해 풀어냈다. 출력을 오름차순 정렬하지 않아 한 번 틀렸다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int nA, nB;
int A[500000], B[500000];

int findB(int n)
{
    int st = 0, ed = nB - 1, m;
    while (st < ed)
    {
        m = (st + ed) / 2;
        if (B[m] < n)
            st = m + 1;
        else
            ed = m;
    }
    if (B[ed] == n)
        return 1;
    return 0;
}

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

    //freopen("nums.txt", "r", stdin);

    cin >> nA >> nB;

    for (int i = 0; i < nA; i++)
        cin >> A[i];
    for (int i = 0; i < nB; i++)
        cin >> B[i];

    sort(B, B + nB);

    vector<int> ans;
    for (int i = 0; i < nA; i++)
    {
        if (!findB(A[i]))
        {
            ans.push_back(A[i]);
        }
    }

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

    sort(ans.begin(), ans.end());
    for (int a : ans)
        cout << a << " ";
    cout << "\n";
}