[백준 1920번] [이분 탐색] [빠른 입출력] 수 찾기

이 문제에서 가장 중요한 지점은, 입출력이 최대 200000 까지 되므로, 빠른 입출력을 활용하여 시간을 출여야 한다.

왜 그렇게 해야하는지에 대해서는 입출력 스트림 관련해서 상당히 복잡하므로, 실력을 키우기 전까지는 그냥 받아들이고 쓰는 것으로 하자.

 

방법은 다음과 같다.

메인함수에 해당 내용을 최상단에 쓰면 된다.

 

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

 

단, 이 방법을 쓰는 경우에는 getchar 같은 것들을 못쓴다는 점은 유의해야 한다.

 

추가적으로 이 문제의 경우에는, 존재하는지 아닌지만 판단해주면 되므로 정렬 후에 이분탐색으로 판단하는 것이 쉽다.

 

해당하는 알고리즘으로 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

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

    int n;
    cin >> n;
    vector<long long> check_value;
    for(int i = 0; i < n; i++){
        long long input_data;
        cin >> input_data;
        check_value.push_back(input_data); 
    } // Input data

    sort(check_value.begin(), check_value.end());

    int m;
    cin >> m;

    for (int j = 0; j < m; j++){
        long long compare;
        cin >> compare;

        int start = 0;
        int end = n;
        int mid;

        //Binary search
        while(start != end){
            int mid = (start + end) / 2;

            if(check_value[mid] < compare){
                start = mid + 1;
            }
            else if(check_value[mid] >= compare){
                end = mid;
            }
        }
        cout << (check_value[start] == compare) << "\n";

    }

    return 0;
}