백준알고리즘 10815 숫자카드 [C++]

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

10815번: 숫자 카드

---

소스코드

#include<iostream>
#include<algorithm>

using namespace std;

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

    int M, N, num;

    cin >> M;
    int *arr = new int[M];
    for(int i = 0; i < M; i++){
        cin >> arr[i];
    }
    
    sort(arr, arr + M);

    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> num;
        if(binary_search(arr, arr + M, num)){
            cout << '1' << ' ';
        }
        else{
            cout << '0' << ' ';
        }
    }
}

 

카드의 수가 최대 50만으로 잡혀있기 때문에 비교시 이분 탐색으로 탐색시간을 줄여야한다. 다행히 C++ binary_search()

를 제공한다. 이분탐색을 위해 모든 요소를 정렬시키는 것도 잊지말자.

 

사용법은 다음과 같다. 함수의 리턴타입은 boolean이다

//binary_search(시작, 끝, 찾는요소);
binary_search(arr, arr + M, num);