[백준 1822] 차집합 (C#, C++) - soo:bak

문제 링크

1822번 - 차집합

설명

자연수로 이루어진 두 집합 A, B가 주어졌을 때,

집합 A에는 속하지만 집합 B에는 속하지 않는 원소들만 골라내어 출력하는 문제입니다.

즉, 차집합 A - B을 구하는 문제입니다.

결과를 오름차순으로 정렬하여 출력해야됨에 유의합니다.

접근법

• 먼저 두 집합을 정렬하여 이진 탐색이 가능한 상태로 만듭니다.
• 집합 A의 각 원소에 대해 집합 B에 존재하는지 이진 탐색으로 확인합니다.
  • 존재하지 않는 경우에만 결과 리스트에 추가합니다.
• 결과는 자연스럽게 오름차순으로 유지되므로 별도 정렬이 필요 없습니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
  static void Main() {
    var inputs = Console.ReadLine().Split().Select(int.Parse).ToArray();
    int n = inputs[0], m = inputs[1];

    var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
    var b = Console.ReadLine().Split().Select(int.Parse).ToArray();

    Array.Sort(a);
    Array.Sort(b);
    var result = new List<int>();

    foreach (var x in a) {
      if (Array.BinarySearch(b, x) < 0)
        result.Add(x);
    }

    Console.WriteLine(result.Count);
    if (result.Count > 0)
      Console.WriteLine(string.Join(" ", result));
  }
}

C++

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

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

  int n, m; cin >> n >> m;

  vi a(n), b(m);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i < m; i++)
    cin >> b[i];

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  vi ans;
  for (int x : a) {
    int s = 0, e = m - 1;
    bool isFound = false;
    while (s <= e) {
      int mid = (s + e) / 2;
      if (b[mid] == x) {
        isFound = true;
        break;
      }
      if (b[mid] < x) s = mid + 1;
      else e = mid - 1;
    }
    if (!isFound) ans.push_back(x);
  }

  cout << ans.size() << "\n";
  for (size_t i = 0; i < ans.size(); i++)
    cout << ans[i] << (i < ans.size() - 1 ? " " : "\n");

  return 0;
}