[57] C 백준 10815번 숫자 카드 문제 (이진탐색, 이분탐색, 정렬)

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

예제 입력 1 

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1 

1 0 0 1 1 0 0 1

 

 

 

<풀이>

이 문제를 처음부터 하나하나 비교해 가는 순차 검색 알고리즘을 통해 풀려고 하였지만 시간초과가 발생할 것 같아 다른 탐색법을 찾아보았다.

이분탐색 혹은 이진탐색이라는 탐색법을 알게 되었는데 이진탐색이란 이렇다.

https://m42-orion.tistory.com/69

[C++ Algorithm] 이분 탐색(Binary Search)

위 블로그 참고

 

이진탐색

이진탐색은 정렬되어있는 리스트에서 탐색범위를 절반씩 줄여가면서 원하는 수를 찾는 방법이다.

 

출처:&nbsp;https://dev-overload.tistory.com/12

이진탐색의 기본 조건은 배열이 무조건 오름차순으로 정렬되어 있어야 한다는 것이다.

 

1(start) 4 7 10 11 13 14(end)의 수열이 있고 타겟값이 7이라고 가정해보자

 

왼쪽부터 순서대로 arr[0], arr[1], arr[2] ... arr[6]이다.

 

start(low)의 위치는 맨 처음 arr[0]이고 end(high)는 맨 뒤 arr[6]로 시작한다.

 

mid = (0 + 6) / 2 이므로 3

 

1 4 7 10 11 13 14

 

3번째 값인 10이 mid의 위치가 된다.

타겟값인 7(2번)이 mid의 값보다 작으므로 end = mid - 1로  재설정 된다.

 

mid = (0 + 2) / 2 = 1 

 

1 4 7 10 11 13 14

 

타겟값인 7(2번)이 mid의 값보다 크므로 start = mid + 1로 재설정 된다. 

 

mid = (2 + 2) / 2 = 2

 

1 4 7 10 11 13 14

 

타겟값인 7(2번)과 mid의 값이 같으므로 타겟값을 찾아내게 되었다.

 

따라서 arr[mid] > target인 경우 end가 mid - 1이 되고,

arr[mid] < target인 경우 start가 mid + 1이 된다.

 

이 문제에서는 (상근이가 가지고 있는지 확인해야 하는 카드)의 배열의 수를 하나씩 (상근이가 가지고 있는 카드)의 오름차순 정렬된 배열에 이진탐색 시켜 카드가 있다면 1, 없다면 0을 출력하게 만들면 된다.

 

<제출한 코드>

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

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현(qsort)
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2)    // a가 b보다 작을 때는
        return -1;      // -1 반환
    
    if (num1 > num2)    // a가 b보다 클 때는
        return 1;       // 1 반환
    
    return 0;    // a와 b가 같을 때는 0 반환
}

int binarySearch(int arr[], int size, int key){ // 이진탐색 함수 (배열, 배열 크기, 타겟값)
    int high, low, mid;
    high = size - 1;
    low = 0;

    while (high >= low){ // high가 low보다 작아지면 값이 없다.
        mid = (high + low) / 2;
        if (key < arr[mid]) high = mid - 1; //key값이 mid값보다 작으면 high = mid - 1이 되어야함.
        else if (key > arr[mid]) low = mid + 1; // key값이 mid값보다 크면 low = mid +1이 되어야함.
        else if (key == arr[mid]) return 1; // key == mid값이면 그 수가 찾던 수이다.
    }
    return 0; // 만족하는 값이 없을 때
}

int main(void){
    int N, M, result;
    int sanggeun[500000];
    int cardCheck[500000];

    scanf("%d", &N);
    for (int i = 0; i < N; i++){
        scanf("%d", &sanggeun[i]);
    }
    scanf("%d", &M);
    for (int j = 0; j < M; j++){
        scanf("%d", &cardCheck[j]);
    }

    qsort(sanggeun, N, sizeof(int), compare); // 이진탐색을 위한 오름차순 정렬

    for (int i = 0; i < M; i++){
        result = binarySearch(sanggeun, N, cardCheck[i]);// 이진탐색 함수
        printf("%d ", result);
    }

    return 0;
}

오름차순 정렬 방법은 <stdlib.h>에 있는 qsort()퀵 정렬 함수를 사용하였다.

퀵 정렬에 대한 내용은 https://dojang.io/mod/page/view.php?id=638

C 언어 코딩 도장: 73.2 퀵 정렬 함수 사용하기