[백준/C++] 1920 수 찾기 (S4)

유형	난이도	완료일	링크	특이사항
이진탐색	실버4	23/03/06	https://www.acmicpc.net/problem/1920

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100000];
int t;

int main(void)
{
	ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);
	
	
	int n; cin >> n;
	for(int i = 0; i<n;i++)
	{
		cin >> arr[i];
	}	
	
	sort(arr,arr+n);
	
	int m; cin >> m;
	
	for(int i =0; i<m; i++)
	{
		cin >> t;
		cout << binary_search(arr, arr+n, t)<<"\\n";
	}
}

최대 100000개의 숫자를 두 번 입력 받고, 두 번째 입력 받은 숫자들이 첫 번째 입력 때 입력 받은 숫자들인지를 1, 0으로 출력해야 한다. 수의 범위가 -21억~21억이므로 배열을 써서 저장하고 확인하는 방법은 불가능하다.

숫자의 범위가 10만개로 O(n^2)의 복잡도를 가지는 탐색은 할 수 없지만 O(n)의 복잡도보다 작은 복잡도를 가지는 탐색은 사용할 수 있다.

<algorithm>에 포함된 함수 binary_search를 이용해 O(logN)의 시간복잡도로 특정 수가 존재하는지 판별할 수 있어서(그 전에 반드시 배열을 sort로 정렬해주어야 한다) binary search를 해야겠다는 생각만 떠올렸다면 쉽게 풀 수 있는 문제였다.