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

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

10815번: 숫자 카드

벡터를 사용하면 시간초과가 나올 것이다.

그래서 셋을 사용했다.

셋은 중복없이 정렬된 상태로 저장이 되고, 셋의 find 함수를 사용할 경우 시간복잡도는 O(logN) 를 가진다.

왜냐하면 셋은 BST(Binary Search Tree, 이진 탐색 트리) 자료구조를 갖고 있기 때문이다.

 

셋의 find 함수의 경우, 해당 원소가 있으면 해당 위치의 iteratior를 반환하고, 원소가 없으면 s.end()를 반환한다.

#include <iostream>
#include <set>

using namespace std;

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

    int n, m, i;
    set<int>s;
    cin>>n;
    while(n--){
        cin>>i;
        s.insert(i);
    }
    cin>>m;
    while(m--){
        cin>>i;
        auto it = s.find(i);
        if(it==s.end()) cout<<0<<' ';
        else cout<<1<<' ';
    }
}