(매일 BOJ) C++ 10815번 숫자카드

이번 문제는 10815번 숫자카드 이다.

접근법

최대로 상근이가 가지고 있는 숫자카드의 개수가 500,000개  판별해야 할 숫자카드의 개수가 500,000개이기에 이를 브루트포스로 푼다면 250억번의 연산이 필요하게 된다. 따라서 이를 해결하기 위해 상근이가 가지고 있는 숫자카드를 정렬한 후 알고리즘 라이브러리의 바이너리 함수을 통해 이분탐색으로 해당하는 값이 있는지 없는지를 판별한다면 TLE가 발생하지 않고 문제를 해결할 수 있다.

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < N; i++){
        int num;
        cin >> num;
        v1.push_back(num);
    } 
    
    sort(v1.begin(),v1.end());
    int M;
    cin >> M;
    bool b;

    for (int j = 0; j < M; j++){
        int num;
        cin >> num;
        b = binary_search(v1.begin(),v1.end(),num);
        if (b) cout << 1 << ' ';
        else cout << 0 << ' ';
    }
}