[ boj : 2776 ] 암기왕

www.acmicpc.net/problem/2776

2776번: 암기왕

문제 : 배열1이 주어지고 배열2가 주어질때 배열 1에 배열2의 수들이 존재하는지 여부를 구하여라

 

해설 : 기초적인 이분탐색 문제입니다.

오랜만에 sort를 직접 구현했습니다. 안짜게 되면 당연스럽게 까먹더라구요. 그래서 상기좀 시킬겸 mergesort를 구현했습니다.

 

#include<bits/stdc++.h>

using namespace std;

int arr[(int)1e6],num[(int)1e6];

void solve();
void mergesort(int l, int r);
void merge(int l, int mid, int r);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}
void solve()
{	
	int n,m;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	mergesort(0, n - 1);
	cin >> m;
	int x;
	for (int i = 0; i < m; i++) {
		cin >> x;
		int ans = 0;
		int l = 0,r=n-1;
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (arr[mid] > x)
				r = mid - 1;
			else if(arr[mid]<x)
				l = mid + 1;
			else {
				ans = 1;
				break;
			}
		}
		cout << ans << "\n";
	}
}
void mergesort(int l, int r)
{
	if (l >= r)return;

	int mid = (l + r) / 2;
	mergesort(l, mid);
	mergesort(mid + 1, r);
	merge(l, mid, r);
}
void merge(int l, int mid, int r)
{
	int p = l, q = mid+1;
	int k = 0;
	while (p <= mid && q <= r)
	{
		if (arr[p] < arr[q])
			num[k++] = arr[p++];
		else
			num[k++] = arr[q++];
	}
	while (p <= mid)
		num[k++] = arr[p++];
	while (q <= r)
		num[k++] = arr[q++];
	k = 0;
	for (int i = l; i <= r; i++)
		arr[i] = num[k++];
}