백준 10815번 : 숫자 카드

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

10815번: 숫자 카드

 

 문제설명 

 

1.  상근이가 가지고있는 숫자 카드 가 주어지고 상근이가 가지고있는지 확인 할 숫자 카드가 주어진다

2. 확인 할 숫자 카드를 순서대로 확인하며 가지고있다면 1을 출력 가지고 있지 않다면 2를 출력한다.

 

 알고리즘 

 

1. 숫자카드 보유여부를 이분탐색으로 구해준다.

 

 코드 

 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(0);
 
    int N;
    cin >> N;
    vector<int> v;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
 
    int M;
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
 
        int low = 0, high = N - 1;
        bool pos = false;
 
        //이분 탐색
        while (low <= high) {
            int mid = (low + high) / 2;
            if (v[mid] == num) {
                pos = true;
                break;
            }
            else if (v[mid] < num)low = mid + 1;
            else high = mid - 1;
        }
 
        if (!pos)
            cout << 0 << " ";
        else
            cout << 1 << " ";
    }
}