본문 바로가기

알고리즘 관련/BOJ

BOJ)10815 숫자 카드

문제: icpc.me/10815


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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)12846 무서운 아르바이트  (0) 2017.01.03
BOJ)12844 XOR  (0) 2017.01.03
BOJ)1733 등번호  (2) 2017.01.03
BOJ)14168 Cow Checklist  (0) 2017.01.03
BOJ)11895 속이기  (0) 2017.01.03