[BOJ/C++] 10815 숫자 카드

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

 

내가 가지고 있는 카드와 주어진 카드를 비교해서 있는지 없는지 확인하면 된다

만약 for문을 돌려 처음부터 끝까지 확인하면 시간복잡도가 O(nm)이 나오므로 최대 n, m = 500,000일 때 최악의 경우 250억 번 비교가 발생한다.. 대신 이진 탐색 트리 기반인 set을 사용하게 되면 find() 연산이 평균/최악 모두 O(log n)으로 개선할 수 있다. 

 

 

#include <iostream>
#include <set>
using namespace std;
int n, m;
set<int> mycard;
int checkcard[500000];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        mycard.insert(k);
    }

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> checkcard[i];
    }

    for (int i = 0; i < m; i++)
    {
        auto it = mycard.find(checkcard[i]);
        if (it != mycard.end())
            cout
                << "1 ";
        else
            cout << "0 ";
    }
}