백준 10815 숫자 카드 / C++

문제 : 10815

풀이 point

N과 M의 범위가 1~500,000이므로 단순 완전탐색은 시간초과이다.

빠른 탐색을 위해 set or map을 통해 상근이가 가지고 있는지 파악한다.
(c++의 경우 set, map은 hash 사용 : 검색, 삽입, 삭제 O(1)/
unordered_set,map은 Red-Black Tree 사용 : 검색, 삽입, 삭제 O(logn))

풀이 방법

상근이의 카드는 set에 집어넣고 M개의 카드들과 상근이의 카드를 비교해나가며 가지고 있는지 파악한다.

코드

//백준 10815, 숫자 카드
#include <iostream>
#include <set>

std::set<int> set;
int card[500'000];
bool ans[500'000];

int main(){

    int N, M;
    std::cin >> N;

    for(int i{0}; i<N; ++i){
        int n;
        std::cin >> n;
        set.insert(n);
    }

    std::cin >> M;

    for(int i{0}; i<M; ++i){
        std::cin >> card[i];
    }

    for(int i{0}; i<M; ++i){
        if(set.find(card[i]) != set.end()) ans[i] = 1;
        else ans[i] = 0;
    }

    for(int i{0}; i<M; ++i){
        std::cout << ans[i] << ' ';
    }

    return 0;
}