[개쉬운 풀이] 백준 10815 숫자 카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

생각

1. 숫자 카드가 최대 500,000 개가 있으므로 정렬을 해야한다.

2. 최대 500,000번을 서치해야 하므로 바이너리 서치를 구현해서 시간을 단축해야한다.

코드

bool binary_search(int x){
    int left = 0,right = n-1;
    while(left <= right){
        int mid = (left + right) / 2;
        if(card[mid] > x){
            right = mid - 1;
        }
        else if(card[mid] < x){
            left = mid + 1;
        }
        else{
            return true;
        }
    }
    return false;
}

기본적인 바이너리 서치이다. 구현 방법을 이해해 놓는 것이 좋다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;

int n;
vector<int> card;
int m;
vector<int> check;

void input(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        card.push_back(tmp);
    }

    sort(card.begin(), card.end());

    cin >> m;
    for(int i = 0; i < m; i++){
        int tmp;
        cin >> tmp;
        check.push_back(tmp);
    }
}

bool binary_search(int x){
    int left = 0,right = n-1;
    while(left <= right){
        int mid = (left + right) / 2;
        if(card[mid] > x){
            right = mid - 1;
        }
        else if(card[mid] < x){
            left = mid + 1;
        }
        else{
            return true;
        }
    }
    return false;
}

void sol(){
    for(int i = 0; i < m; i++){
        cout << binary_search(check[i]) << " ";
    }
}

int main(){
    input();
    sol();
}