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

#문제

#풀이

#include <iostream>
#include <unordered_set>

using namespace std;

unordered_set<int> cardSet;

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

	int N, M;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		int x;
		cin >> x;

		cardSet.insert(x);
	}

	cin >> M;

	for (int i = 0; i < M; ++i)
	{
		int x;
		cin >> x;

		cout << (cardSet.count(x) == true ? 1 : 0) << ' ';
	}

	return 0;
}

#정리

첫 입력에서는 내가 가진 카드를, 두 번째 입력에서는 보유 여부를 확인하는 카드의 숫자가 입력된다. 입력 여부에 맞춰 1과 0을 출력하면 되는 문제이다. 내가 가진 카드를 모두 순회하게 되면 O(N*M)이 되므로 매우 비효율적이다. unordered_set(hash set)을 사용하면 O(N+M)으로 효율적인 결과를 도출할 수 있다.

#문제

#풀이

#정리

Enjoy Reading This Article?