[백준 1822] 차집합

www.acmicpc.net/problem/1822

1822번: 차집합

이분탐색을 사용하는 문제

a와 b 둘다 set이므로 집합 내에서 겹치는 숫자는 존재하지 않는다.

1. a의 입력을 받고

2. b의 입력을 이분탐색으로 찾아서 겹치면 배열 인덱스를 표시 + 겹치는 숫자 표시

3. 출력

 

문제를 제대로 안읽어서 더 틀렸다...

a와 b가 전부 겹치면 0만 출력하는 것!

#include <stdio.h>
#include <algorithm>
using namespace std;

int arr[500000];
int check[500000];
int main(void)
{
  int n, m, sze = 0;
  scanf("%d %d", &n, &m);

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  sort(arr, arr + n);

  for (int i = 0; i < m; i++)
  {

    int l = 0, r = n - 1;

    int tmp;
    scanf("%d", &tmp);

    if (arr[l] > tmp || arr[r] < tmp)
    {
      continue;
    }

    while (l <= r)
    {
      int mid = (l + r) / 2;
      if (arr[mid] < tmp)
      {
        l = mid + 1;
      }
      else if (arr[mid] > tmp)
      {
        r = mid - 1;
      }
      else
      {
        check[mid] = 1;
        sze++;
        break;
      }
    }
  }

  if (sze == n)
  {
    printf("0\n");
  }
  else
  {
    printf("%d\n", n - sze);
    for (int i = 0; i < n; i++)
    {
      if (check[i] != 1)
      {
        printf("%d ", arr[i]);
      }
    }
  }
  return 0;
}