[BOJ 1920] 수 찾기

1) 문제 링크

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

2) 접근

이진 탐색을 구현해야 O(NlogM)으로 빨리 끝내버릴 수 있겠다고 생각했다. 그래서 입력받은 정수들을 오름차 순으로 정렬한 뒤 BinarySearch(num) 함수를 만들어 이진탐색을 돌렸다.

3) 풀이

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int key;
long long A[100001];

// 이진탐색 함수
int BinarySearch(int num){
    int s=0, e=N-1;
    int mid;

    while(s <= e){
        mid = (s+e) / 2;
        if(num == A[mid]) { return 1; }
        else if(num > A[mid]) { s = mid + 1; }
        else { e = mid - 1; }
    }
    return 0;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;

    for(int i=0; i<N; ++i){ cin >> A[i]; }
    sort(A, A+N);

    cin >> M;

    for(int i=0; i<M; ++i){
        cin >> key;
        cout << BinarySearch(key) << '\n';
    }

    return 0;
}

4) 피드백

처음 이 글을 작성했을 당시(올해 2월? 쯤)에는 이진탐색을 외워야겠다는 생각만 하고 있었다. 물론 외워서 활용할 줄 아는 것도 필수적이긴 하지만… <algorithm> 헤더에 lower_bound(), upper_bound() 함수가 있다는 것도 기억하도록 하자.