[BOJ / C++] 숫자 카드 (이분탐색)

문제링크: https://www.acmicpc.net/problem/10815

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> card(n);
    for (int i = 0; i < n; i++) {
        cin >> card[i];
    }
    sort(card.begin(), card.end());

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

    for (int k: arr) {
        cout << binary_search(card.begin(), card.end(), k) << ' ';
    }
}

 

 

2. 시간복잡도

m = 500,000 이고, n = 500,000 이므로 만약 m의 경우마다 n을 선형탐색한다면 O(mn) = 25 * 10^10으로 시간초과가 된다. 따라서 O(mlgn) 이 되도록 해야하고, 이분탐색을 이용하면 된다. mlgn = 5*10^5 * 20 < 10^8 이므로 시간제한 1초 안에 통과한다.

 

3. 분석

시간복잡도를 낮추기 위해 이분탐색을 사용하면 된다. STL binary_search를 사용하면 된다.