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

시간 복잡도

• N의 크기가 최대 500,000 입니다.
• 정렬과 이분탐색을 이용해 $O(nlogn + logn)$의 시간복잡도로 해결할 수 있습니다.

문제 접근법

• 입력받은 숫자를 정렬합니다.
• 상근이가 가지고 있는지 정렬된 숫자 카드중에 이분탐색으로 찾습니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>


using namespace std;

using int32 = long;
using int64 = long long;

static vector<int> v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;

    cin >> N;
    v.resize(N);

    for (int i = 0; i < N; i++)
        cin >> v[i];

    cin >> M;

    sort(v.begin(), v.end());

    for(int i=0; i<M; i++)
    {
        int num;
        cin >> num;

        int l = 0, r = N-1;
        int mid;
        bool flag = false;
        while(l<=r)
        {
            mid = (l + r) / 2;
            if (num == v[mid])
            {
                flag = true;
                break;
            }
            else if(num > v[mid])
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        cout << flag << ' ';
    }



    return 0;
}