백준 1920번: 수 찾기

1. C 스타일 입출력 vs C++ 스타일 입출력 차이점

scanf, printf보다 cin, cout의 속도가 느려서 cin, cout을 사용하면 시간 초과된다.

아래 코드를 실행해서 cin, cout의 속도를 높여주거나 scanf, printf 를 사용하자.

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ios::sync_with_stdio , cin.tie , cout.tie 사용법과 설명, 속도 비교

2. const & 로 속도 개선과 메모리 절약

bool binarySearch(const vector<int>& arr, int target)

함수의 파라미터로 const &를 사용했다. const는 상수 표현으로, 값을 바꿀 필요가 없을 때 사용한다. 컴파일러는 해당 변수가 절대 변경되지 않는다는 것을 보장받기 때문에 불필요한 메모리 접근을 줄이거나 더 효율적인 코드로 변환할 수 있다.

&(레퍼런스)는 매개변수로 인자값을 복사해오는 것이 아니라 인자값에 직접 접근함으로써 속도를 높이고 메모리를 절약할 수 있다.

 

정답 코드

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

bool binarySearch(const vector<int>& arr, int target)
{
	int left = 0;
	int right = arr.size() - 1;
	while (left <= right)
	{
		int mid = (left + right) * 0.5;
		if (arr[mid] == target)
		{
			return true;
		}
		else if (target < arr[mid])
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return false;
}

int main()
{
	int N;
	scanf("%d", &N);

	vector<int> A;
	for (int i = 0; i < N; i++)
	{
		int num;
		scanf("%d", &num);
		A.push_back(num);
	}
	sort(A.begin(), A.end());

	int M;
	scanf("%d", &M);
	for (int i = 0; i < M; i++)
	{
		int num;
		scanf("%d", &num);
		if (binarySearch(A, num))
		{
			printf("1\n");
		}
		else
		{
			printf("0\n");
		}
	}
	return 0;
}