BOJ)10815 숫자 카드

문제: icpc.me/10815

N개의 카드와 M개의 카드가 있을 때 M개의 카드 들이 각각 N개에 카드에 속해 있나 확인하는 문제이다.

O(NM)의 방법으로 풀 경우 TL을 받으므로 binary_search를 이용하여 O(logNM)의 방법으로 해결하면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, x;
vector<int> vt;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        vt.push_back(x);
    }
    sort(vt.begin(), vt.end());
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &x);
        if (binary_search(vt.begin(), vt.end(), x))
            printf("1 ");
        else
            printf("0 ");
    }
    return 0;
}