백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)

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

아이디어

• 포함하고있는지 확인 >> 이분탐색

시간복잡도 계산

• N개에 대해 정렬 : O(NlgN)
• M개에 대해 이분 탐색 : O(M * lgK )
• 합 : O(NlgN + MlgK)

인트 계산

• 각 숫자의 최소 -1e7, 최대 1e7 > INT 가능

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int nums[500010];
 
 
void binsearch(int st, int en, int tar) {
    if(st==en) {
        if(nums[st] == tar) cout << 1 << ' ';
        else cout << 0 << ' ';
        return;
    }
    
    int mid = (st+en)/2;
    
    if(nums[mid] < tar) binsearch(mid+1, en, tar);
    else binsearch(st, mid, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> nums[i];
    
    sort(nums, nums+N);
    
    int M; cin >> M;
    for(int i=0; i<M; i++){
        int a; cin >> a;
        binsearch(0,N-1,a);
    }
}
 

문제유형

• 이분탐색 기본