백준 : 1822번 차집합-이분탐색 (c++)

백준 링크

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

1822번: 차집합

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	9096	4044	3257	45.719%

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

예제 입력 1

4 3
2 5 11 7
9 7 4

예제 출력 1

3
2 5 11

예제 입력 2

3 5
2 5 4
1 2 3 4 5

예제 출력 2

0

코드 풀이

• 입력값으로 주어진 집합 원소의 개수 A, B와 집합 A, B의 값을 할당
• A를 B에 대조해야하기 때문에 B집합을 정렬
• 이분탐색 시작 (A원소값 탐색)
• A원소값이 B집합에 없다면 set 자료구조에 저장(키값만을 사용하고 자동 정렬의 이점)
• 최종 답 출력

코드

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

using namespace std;

int ACount, BCount;

vector<int> vecASet;
vector<int> vecBSet;

void InputFunc()
{
    cin >> ACount >> BCount;

    vecASet.resize(ACount);
    vecBSet.resize(BCount);

    for (int i = 0; i < ACount; ++i)
    {
        cin >> vecASet[i];
    }

    for (int i = 0; i < BCount; ++i)
    {
        cin >> vecBSet[i];
    }
}

bool Binary_SearchFunc(int Target)
{
    int Start = 0;
    int End = vecBSet.size() - 1;

    while (Start <= End)
    {
        int Mid = (Start + End) / 2;

        if (vecBSet[Mid] == Target)
        {
            return true;
        }
        else if (vecBSet[Mid] < Target)
        {
            Start = Mid + 1;
        }
        else
        {
            End = Mid - 1;
        }
    }

    return false;
}

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

    // 입력
    InputFunc();

    // B집합 정렬
    sort(vecBSet.begin(), vecBSet.end());

    set<int> ResultSet;

    for (auto Target : vecASet)
    {
        if (!Binary_SearchFunc(Target))
        {
            ResultSet.insert(Target);
        }
    }

    if (ResultSet.size() == 0)
    {
        cout << 0;
    }
    else
    {
        cout << ResultSet.size() << '\n';
    }

    for (auto Numb : ResultSet)
    {
        cout << Numb << ' ';
    }

    return 0;
}