10815번 - 숫자 카드

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

10815번: 숫자 카드

풀이는 두 가지로 풀었다.

1) set을 활용. 중복인지 찾으려고 활용하였다.

#include <iostream>
#include <set>

using namespace std;

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

	int n, m;
	set<int> s;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		s.insert(a);
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int a;
		cin >> a;
		if (s.find(a) != s.end())
			cout << 1 << ' ';
		else
			cout << 0 << ' ';
	}
	
	return 0;
}

하지만 set의 원소 갯수만큼을 다 뒤져야하기 때문에 시간이 n^2이 걸린다.

2) binary search, 즉 이분 탐색을 활용.

이분 탐색을 활용하면 log n 이므로 시간이 단축된다.

이분탐색의 주의점은 정렬이 되어있어야 활용이 가능하다.

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

using namespace std;

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

	int n, m;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v[i] = a;
	}
	sort(v.begin(), v.end());
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int a;
		cin >> a;
		if (binary_search(v.begin(), v.end(), a))
		{
			cout << 1 << ' ';
		}
		else
			cout << 0 << ' ';
	}
	
	return 0;
}