cpp) 백준 1920: 수 찾기

Problem

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

1920번: 수 찾기

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내시오.

 

 

Solution

#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int arr[100001];

void binarySearch(int key){
    int start = 0;
    int end = n-1;
    int mid;

    while(start<=end){
        mid = (start+end)/2;
        if(arr[mid]==key){
            cout << 1 << '\n';
            return ;  // 함수 종료
        } else if(arr[mid]>key){
            end = mid-1;
        } else {
            start = mid+1;
        }
    }
    cout << 0 << '\n';
}


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

    cin >> n;
    for(int i=0;i<n;i++)
        cin >> arr[i];
    
    sort(arr, arr+n);  // 이진탐색의 선행조건은 먼저 정렬이 되어있어야 한다는 것

    cin >> m;
    int num;
    for(int i=0;i<m;i++){
        cin >> num;
        binarySearch(num);
    }

    
   return 0;
}

 

선형탐색으로 풀면 시간 초과가 날 수 있기 때문에 시간복잡도가 O(logN)인 이진탐색(Binary Search)을 이용해 풀어야 한다. 이 문제에서는 cin과 cout을 썼지만 코드 실행 속도가 중요한 대회에서는 scanf, printf를 사용하는 게 유리하다. 

 

 

Reference

https://chanqun.tistory.com/14

백준 1920번 : 수 찾기 (c++ 시간 초과 해결)