[백준/C++][수 찾기 - 1920]

문제

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

1920번: 수 찾기

문제 풀이

M개를 N번을 탐색하게 된다면 시간복잡도가 N^2이므로 시간초과가 난다. 그래서 이분탐색을 사용하여 NlogN으로 풀었다.

이분탐색만 사용하면 풀 수 있는 간단한 문제였다.

입력을 받을때 원래 cin 받았는데 시간초과가 나서 scanf으로 입력받고 출력도 printf로 하니까 시간초과 문제도 해결하였다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
vector<int> a;
int solve(int num){
    int mid,right,left;
    right = a.size()-1;
    left = 0;
    mid = (right+left)/2;
    int result = 0;
    while(right-left>=0){
        if(a[mid] == num){
            result = 1;
            break;
        }
        else if(a[mid] > num){
            right = mid-1;
        }
        else if(a[mid]<num){
            left = mid+1;
        }
        mid = (right+left)/2;
    }
    return result;
}
int main(void){
    int N,M;
    cin >> N;
    for(int i = 0;i<N;i++){
        int num;
        cin >> num;
        a.push_back(num);
    }
    sort(a.begin(),a.end());
    cin >> M;
    for(int i = 0;i<M;i++){
        int num;
        scanf("%d",&num);
        // cout << num << "\n";
        printf("%d\n",solve(num));
    }
}