백준 - 1920번 수 찾기

백준 1920번 수 찾기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

자연수 N(1 <= N <= 100000)이 주어집니다. 이후 N개 정수가 주어집니다
이후 자연수 M(1 <= M <= 100000)이 주어집니다. 이후 M개 정수가 주어지는데 이 수들이 N개의 정수들 안에 포함되는지 구해야합니다.
모든 정수의 범위는 -2^31보다 크고 2^31보다 작다.

문제 풀이

배열만 사용하기에는 음수가 존재하기 때문에 이분탐색을 통해 특정 값을 빠르게 찾아줍니다.
이분탐색을 하기 전, 오름차순이나 내림차순으로 정렬해주어야 합니다.

만약 출력이 너무 많아 시간초과가 생긴다면, 입출력 객체 가속을 시켜 빠르게 답을 출력하도록 해줍니다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<int> v;

int solve(long long int num)
{
	int high = n - 1;
	int low = 0;

	while (low <= high)
	{
		int mid = (high + low) / 2;

		if (v[mid] == num)
			return 1;

		if (v[mid] > num)
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;			
		}
	}
	return 0;
}

int main()
{
	//입촐력 객체 가속(더 빠르게 출력할 수 있음)
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	long long int t;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> t;
		v.push_back(t);
	}

	sort(v.begin(), v.end());

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> t;
		printf("%d\n", solve(t));
	}
}

출저

https://www.acmicpc.net/problem/1920