[C언어] 백준 10815번: 숫자 카드

• 문제

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

---

• 코드

#include <stdio.h>
#include <stdlib.h>
// 백준 10815번: 숫자 카드

int compare(const void *a, const void *b){
    return (*(int*)a - *(int*)b);
}

int BinarySearch(int arr[], int size, int target){
    int left = 0;
    int right = size - 1;

    while(left <= right){
        int mid = left + (right - left) / 2;

        if(arr[mid] == target){
            printf("1 ");
            return 0;
        }

        if(arr[mid] < target){
            left = mid  + 1;
        }
        else{
            right = mid - 1;
        }

    }

    printf("0 ");
    return 0;
}

int main(){

    int n;
    scanf("%d", &n);
    
    int arr1[n];

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

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

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

    for(int i = 0; i < m; i++){
        BinarySearch(arr1, n, arr2[i]);
    }



    return 0;
}

---

• 문제풀이방법

1. n개와 m개의 카드를 각각 배열에 저장한다. (이하 arr1, arr2라고 칭함)
2. C언어 내장함수인 qsort를 활용하여 arr1을 오름차순으로 정렬한다.
3. arr2에 있는 숫자 카드 하나씩 이분 탐색을 이용하여 arr1에 있나 확인한다.
4. 만약 arr2의 숫자 카드가 arr1에 있다면 1 출력, 없다면 0 출력

이분 탐색 잘 모르신다면 아래 참조

이분 탐색 (Binary Search)