<백준> 1920 수 찾기 / C++ 풀이

중점

1. 넓은 범위 내에서 숫자를 찾는다. 이때 시간 제약은 1초이다.

2. 숫자의 존재 여부만을 알아내면 된다.

 

넓은 범위 내에서 숫자를 찾아야 한다. 이때 1초라는 시간내에 숫자의 존재 유무를 찾아야한다. 따라서 이분 탐색을 이용해서 빠른 시간내에 찾아야 되겠다는 생각을 했다. 따라서 입력받는 숫자를 배열에 저장 후 sort를 진행한 후 이분탐색을 진행한다.

 

---

 

#include <bits/stdc++.h>

using namespace std;

int a[100005];
int n;

int binary_search(int target){
    int st = 0;
    int ed = n - 1;

    while (st <= ed)
    {
        int mid = (st + ed) / 2;

        if (a[mid] < target){
            st = mid + 1;
        } else if (a[mid] > target){
            ed = mid - 1;
        } else {
            return 1;
        }
    }

    return 0;
}

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

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> a[i];
    }

    sort(a, a + n);

    int m;
    cin >> m;

    while (m--)
    {
        int t;
        cin >> t;
        cout << binary_search(t) << '\n';
    }
}

 

위 코드에서는 binary_search라는 이분 탐색 함수를 만들었다. 혹은 c++에서 제공하는 이분 탐색 함수를 사용해도 된다.

 

감사합니다.