[C++] 백준 10815번: 숫자 카드

문제 링크

10815번: 숫자 카드

문제 요약

상근이가 가지고 있는 N개의 카드가 주어진다. 이후 M개의 카드가 주어졌을 때, 상근이가 이 카드들을 가지고 각각 있는지 구해야 한다.

접근 방법

단순이 상근이가 가지고 있는 카드가 먼저 나열되고, 후에 제시되는 카드들이 그 목록 안에 있는지 확인하면 되는 문제입니다. 여러가지 접근이 가능합니다.

1. 정렬 후, 이분 탐색
2. 셋
3. 크기가 20000001인 배열 선언

위에서부터 순서대로 배열, std::unordered_set, std::binary_search를 사용한 결과입니다.

코드1(std::binary_search)

#include <bits/stdc++.h>

using namespace std;

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

	int n, m;
	cin >> n;

	vector<int> v, res;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());
	cin >> m;

	while (m--)
	{
		int num;
		cin >> num;
		if (binary_search(v.begin(), v.end(), num))
			res.push_back(1);
		else
			res.push_back(0);
	}

	for (auto& i : res)
		cout << i << ' ';
	return 0;
}

코드2(std::unordered_set)

#include <bits/stdc++.h>
#include <unordered_set>

using namespace std;

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

	int n, m;
	cin >> n;

	unordered_set<int> s;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		s.insert(num);
	}

	cin >> m;
	vector<int> res;
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		res.push_back(s.find(num) != s.end() ? 1 : 0);
	}

	for (auto& i : res)
		cout << i << ' ';
	return 0;
}

코드3(배열)

#include <bits/stdc++.h>

using namespace std;

bool arr[20000001];

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

	int n, m;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		arr[num + 10000000] = true;
	}

	cin >> m;
	vector<int> res;
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		res.push_back(arr[num + 10000000] ? 1 : 0);
	}

	for (auto& i : res)
		cout << i << ' ';
	return 0;
}