[백준] 1822번 차집합

문제: 1822번: 차집합

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

bool binarySearch(int target, vector<int>& B) {
    int st = 0;
    int en = B.size() - 1;

    while (st <= en) {
        int mid = (st + en) / 2;

        if (B[mid] == target)
            return true;
        else if (B[mid] > target)
            en = mid - 1;
        else
            st = mid + 1;
    }
    // 여기까지 도달하면 false 리턴해
    // A 의 요소가 B 에 존재하지 않아여
    return false;
}

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

    int nA, nB;
    cin >> nA >> nB;

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

    // 일단 B 오름차순 정렬해
    sort(B.begin(), B.end());
    sort(A.begin(), A.end());

    // 이제 A 를 for 문으로 전체 돌면서 이분탐색해
    // B 에 A 의 요소가 존재하면 cnt 값 증가시키고 answer 에 넣어
    queue<int> answer;
    for (int i = 0; i < nA; i++) {
        if (!binarySearch(A[i], B)) {
            // A 의 요소가 B 에 존재하지 않으면 cnt 값 증가시ㅕㅋ
            answer.push(A[i]);
        }
    }
    cout << answer.size() << "\n";
    while (!answer.empty()) {
        cout << answer.front() << " ";
        answer.pop();
    }

    return 0;
}

 

A 에는 존재하지만 B 에는 존재하지 않는 값을 찾으려면 for 문으로 A 돌면서 B 에 대해 이분탐색 돌리면 된다.