[백준 10815] 알고리즘 59일차 : 숫자 카드

www.acmicpc.net/problem/10815

10815번: 숫자 카드

C++ 이분탐색

쉬운 이분탐색 응용없이 그냥 이분탐색만 하면 되는 문제

이건..실버4이기엔 쉬운 문제인 것 같다.

 

접근방법

상근이가 갖고 있는 숫자카드는 배열로 받아서 정렬해주고

주어지는 정수 M은 바로 받아서 이분탐색하는 것 끝

 

오답노트

내가 코드를 잘 못짜서 그런건지는 모르겠지만 일단 기본 코드는 시간초과 났었고

sync_with_stdio 해주고 cin tie해주니까 통과됐다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int sg[500000];
int n;
int isinsg(int num){
    int s = 0;
    int e = n-1;
    int mid;
    while(s <= e){
        mid = (s+e)/2;
        if(sg[mid] == num){
            return 1;
        }else if(sg[mid] > num){
            e = mid-1;
        }else{
            s = mid+1;
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> sg[i];
    }
    sort(sg, sg+n);
    
    int m, num;
    cin >> m;
    for(int i = 0 ; i < m ; i++){
        cin >> num;
        cout << isinsg(num) << " ";
    }
    return 0;
}