[백준] 10815(숫자 카드) c언어

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

---

 

 

이진 탐색 + 오름차순 정렬

https://butter-shower.tistory.com/8

https://h-factory.tistory.com/694

 

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int x, y;
} Point;

int compare(const void *a, const void *b){
    Point p1 = *(Point*)a, p2 = *(Point*)b;
    if (p1.x < p2.x)
        return -1;
    else if (p1.x > p2.x)
        return 1;
    else {
        if (p1.y < p2.y)
            return -1;
        else if (p1.y > p2.y)
            return 1;
        return 0;
    }
}

int binsearch(int data[], int n, int key) {
  int low, high, mid;
  low = 0;
  high = n-1;
  while(low <= high) {
    mid = (low + high) / 2;
    if(key == data[mid]) {
      return mid;
    } else if (key < data[mid]) {
      high = mid - 1;
    } else if (key > data[mid]) {
      low = mid + 1;
    }
  }
  return -1;
}

int main(void) {

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

  int *arr, *ans;
  arr = (malloc)(sizeof(int) * n);
  int index;

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

  qsort(arr, n, sizeof(int), compare);

  int m;
  scanf("%d", &m);
  int key = 0;
  ans = (malloc)(sizeof(int) * m);

  for(int i=0; i<m; i++) {
    scanf("%d", &key);
    index = binsearch(arr, n, key);
    if(index == -1) 
      ans[i] = 0;
    else 
      ans[i] = 1;
  }

  for(int i=0; i<m; i++) 
    printf("%d ", ans[i]);

  free(arr);
  free(ans);

  return 0;
}