[백준] 10815 숫자카드

 

 

 

이중 for문을 사용할 시 500000*500000의 엄청난 크기가 나와서 이진탐색으로 풀어야 한다. 

간단한 이진탐색이기 때문에 큰 어려움은 없었지만 까먹어서 구현하는데 오래걸렸다,,

*********까먹지 않기 위해 개인적으로 정리할 예정!!!***********8

이외에도 시간초과가 계속 뜨는 바람에 계속 수정을 했다.. 수정한내용은 다음과 같다.

1. 입/출력에 시간을 많이 잡아먹어서 ios::sync_with_stdio(false); cin.tie(0); 추가

2. 기존에 쓰던 벡터에서 일반배열로 수정

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cstdio>
 
using namespace std;
 
int n, m;
int sangen[500001];
 
int BSearch(int target) 
{
    int low = 0;
    int high = n-1;
    int mid;
 
    while (low <= high)
    {
        mid = (low + high) / 2;
 
        if (sangen[mid] == target)
            return 1;
        else if (sangen[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return 0;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> sangen[i];
    }
 
    sort(sangen,sangen+n);
 
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int number;
        cin >> number;
        cout << BSearch(number) << " ";
    }
    
    return 0;
}