[BaekJoon] 1920번 : 수 찾기

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 이 문제는 간단하게 map, set STL을 사용해서 풀면 시간초과가 납니다.
• 이진탐색 트리로 삽입, 정렬 과정에서 시간이 더 걸려서 이진탐색과 시간복잡도는 O(logN)으로 같지만 느립니다.
• 이진탐색 코드를 아래와 같이 직접 구현해도 되지만, STL의 binary_search 함수를 사용하면 보다 편리합니다.
• c, c++ stream 동기화 끄는 코드와 버퍼 비워주는 코드도 있어야 시간초과가 나타나지 않습니다.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int arr[100005];
    int num;
    cin>>num;
    
    for(int i=0;i<num;i++){
        cin>>arr[i];
    }
    sort(arr, arr+num);
    int m;
    cin>>m;
    
    for(int i=0;i<m;i++){
        int n;
        cin>>n;
        cout<<binary_search(arr, arr+num,n)<<"\n";
    }
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.