백준 1920 수 찾기 / C++

문제 : 1920

풀이 point

map, set 또는 이진 검색을 활용하여 풀이를 진행할 수 있다.

N개의 요소를 set에 저장한 뒤 M개의 요소가 N개의 있는지 확인하면 된다.

이진 검색의 경우 A배열을 정렬한 뒤 평범하게 구현하면 된다.

코드

//백준 1920, 수 찾기

#include <iostream>
#include <algorithm>

int A[100'000];
int B[100'000];

int N, M;

void binarySearch(int i){
    int start{0}; int end{N-1};
    while(start <= end){
        int mid = (start + end) / 2;
        if(B[i] > A[mid]){
            start = mid+1;
        }
        else if(B[i] < A[mid]){
            end = mid-1;
        }
        else{
            std::cout << 1 << '\n';
            return;
        }
    }
    std::cout << 0 << '\n';
}

int main (){

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

    std::sort(A, A+N);

    for(int i{0}; i<M; ++i){
        binarySearch(i);
    }
    
    return 0;
}

2025-01-26T02:07:07.954Z