[BOJ]1920번: 수 찾기

문제 풀러 가기 링크

1920번: 수 찾기

이분 탐색을 이용하면 된다. 나는 속도가 60ms가 나왔는데 적게 나오신 분들의 코드를 보니 입력 받는 부분이 특이하던데 어떻게 하는지는 모르겠다.

이분탐색에서 int mid = (left + right) / 2하는 부분에서 / 2 부분을 쉬프트 연산자를 써서 >> 1로 바꿔주니 나의 경우에는 64ms -> 60ms로 바뀌었다.

코드

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N, M, A[100001], B[100001];
	inline bool bs(int left, int right, int n)
	{
	while (left <= right)
	{
	int mid = (left + right) >> 1;
	if (A[mid] < n)
	left = mid + 1;
	else if (A[mid] > n)
	right = mid - 1;
	else {
	return true;
	break;
	}
	}
	return false;
	}
	int main()
	{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
	scanf("%d", &A[i]);
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++)
	{
	scanf("%d", &B[i]);
	}
	sort(A, A + N);
	const int end = N - 1;
	for (int i = 0; i < M; i++) {
	if (bs(0, end, B[i]))
	printf("1\n");
	else
	printf("0\n");
	}
	return 0;
	}

view raw 1920.cpp hosted with ❤ by GitHub