백준 1920 - 수 찾기

문제 자체는 단순하게 수가 있는지 없는지 찾으면 되지만, 시간 제한이 짧게 걸어져 있어 정렬과 이진탐색을 사용하지 않으면 시간초과로 해결할 수 없는 문제입니다.

#include <iostream>
#include <algorithm>

bool cmp(int a, int b) {
	if (a < b) return true;
	else return false;
}

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

	int n;
	std::cin >> n;
	
	int* nums = new int[n];
	for (int i = 0; i < n; i++)
		std::cin >> nums[i];

	//int min;
	//for (int i = 0; i < n; i++)
	//{
	//	min = i;

	//	for (int j = i + 1; j < n; j++)
	//	{
	//		if (nums[min] > nums[j])
	//			min = j;
	//	}

	//	int temp = nums[i];
	//	nums[i] = nums[min];
	//	nums[min] = temp;
	//}

	std::sort(nums, nums + n, cmp);

	int m;
	std::cin >> m;

	int* m_nums = new int[m];
	for (int i = 0; i < m; i++)
		std::cin >> m_nums[i];

	for (int i = 0; i < m; i++)
	{
		int left = 0;
		int right = n - 1;

		bool isAvail = false;
		while (left <= right)
		{
			int mid = (left + right) / 2;

			if (nums[mid] == m_nums[i])
			{
				isAvail = true;
				break;
			}
			else if (nums[mid] < m_nums[i])
				left = mid + 1;
			else
				right = mid - 1;
		}

		if (isAvail)
			std::cout << "1\n";
		else
			std::cout << "0\n";
	}

	return 0;
}