BOJ 1920 수 찾기

N개의 수 중에서 M 개의 수가 존재하는지 여부를 0,1로 출력하는 문제이다. 총 M 개의 수가 N에 존재 하는지 알기 위해서 브루트포스 알고리즘을 사용한다면 N*M 즉 10000000000으로 시간초과가 발생한다. 때문에 이분탐색으로 logN 의 시간복잡도를 활용하여 문제를 풀어야 한다. 

 

입력 N은 정렬되어 들어오지 않기 때문에 이분탐색을 위해 정렬이 필요하다.

처음에 STL algorithm에 있는 sort를 활용하여 정렬하였는데 제출하고 나니 시간초과가 발생하였다.

원인이 뭔지 찾아보다가 어떤 사람은 qsort를 직접 구현하면 된다고 하는데, 실제 qsort는 STL에서 제공하는 sort보다 시간이 느리다. 한참 찾아보다가 발견한 원인은 재귀함수 파라미터에 vector를 call by reference 가 아닌 call by value로 하고 있었다. 

 

아무튼 위에 문제를 해결하여 성공하였다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> arr(100001,0);

int binarySearch(int start, int end, int n)
{
	if(start == end)
	{
		if(arr[start] == n)
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}

	int mid = (start + end) / 2;
	if(n < arr[mid])
	{
		return binarySearch(start, mid, n);
	}
	else if(n > arr[mid])
	{
		return binarySearch(mid + 1, end, n);
	}
	else
	{
		return 1;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	sort(arr.begin(),arr.begin()+n);

	cin >> m;

	vector<int> search(m,0);

	for(int i = 0; i < m; i++)
	{
		cin >> search[i];
	}

	for(int i = 0; i < m; i++)
	{
		cout << binarySearch(0, n - 1, search[i]) << "\n";
	}
}