baekjoon - (숫자 카드)

문제 번호 : 10815번

난이도 : Silver 5

 

시간 제한메모리

2 초

256 MB

 

문제

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

 

 

풀이)

이 문제는 그냥 생각해보면 이중 반복문으로 M을 하나씩 검사하면서 N과 같은지 찾아보고 같으면 1을 아니면 0을 내어주면 된다.

 

하지만 이중반복문을 사용할 시 시간초과가 날 것이다. 이 문제의 시간 제한은 2초이고, 10^8 * 2 이다. 

이중 반복문을 사용할 시 (10^7 * 2) * (10^5 * 5) 가 된다 대략적으로 봐도 2초를 훌쩍 넘기는 시간이다.

 

그렇다면 여기서 이진 탐색을 사용할 수 가 있다.

이진 탐색은 반씩 제거하면서 N번을 탐색할 것을 logN이 걸리기 때문에 훨씬 시간이 줄어든다.

단! 이진 탐색은 정렬 되어 있는 수에 대해서만 가능하기 때문에 정렬을 해서 탐색이 가능한지에 대해서 잘 봐야하는게 특징이다.

 

N을 찾을 거기 때문에 N을 정렬하고, M만큼 반복문을 돌면서 이진탐색으로 N의 배열을 검사하면 된다.

low, mid, high를 정해놓고, low와 high를 mid만큼 계산해주면 된다.

 

코드)

#include <bits/stdc++.h>
using namespace std;

int bsearch(int target, vector<int> &arr1){
    int low = 0;
    int high = arr1.size()-1;
    int mid;
    
    while(low <= high){
        mid = (low + high) / 2;
        
        if(target == arr1[mid]){
            return 1;
        }else if(target < arr1[mid]){
            high = mid - 1;
        }else if(target > arr1[mid]){
            low = mid + 1;
        }
        
    }
    return 0;
}

int main() {
    int N;
    cin >> N;
    vector<int> arr1(N);
    for(int i=0; i<N; i++){
        cin >> arr1[i];
    }
    
    int M;
    cin >> M;
    vector<int> arr2(M);
    for(int i=0; i<M; i++){
        cin >> arr2[i];
    }
    sort(arr1.begin(), arr1.end());
    
    for(int i=0; i<arr2.size(); i++){
        cout << bsearch(arr2[i], arr1) << " ";
    }
    
    
    return 0;
}