[C/C++] 백준 #1920 수 찾기(이진 탐색)

주어진 수열에서 M개의 데이터 중에 해당 수가 존재하는지 여부를 가리는 문제입니다.

 

집합 자료를 이용하면 손쉽게 구현할 수 있고, 또는 정렬 후 이진 탐색을 통해서도 이루어질 수 있습니다.

해시 집합 자료를 이용하면, 이론적으로 \(O(N+M)\)의 효율로 구현될 수 있습니다.  이진트리 집합 자료인 경우에는 \(O((N+M) \log N)\)이 걸립니다.  \( \log N \) 자체가 큰 로드가 아니므로 사실상 집합 자료를 사용해도 되고, 정렬 후 이진 탐색을 사용해도 됩니다.

 

저는 정렬 후 이진 탐색을 이용해서 구현했습니다.  알고리즘 효율은 \(O( (N+M) \log N )\)입니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1920
//        - by Aubrey Choi
//        - created at 2019-06-30
//------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, m, v[100000], s;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &v[i]);
    std::sort(v, v + n);
    scanf("%d", &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &s);
        printf("%d\n", (int)std::binary_search(v, v + n, s));
    }
    return 0;
}