[백준/C++] 2776번 암기왕

문제링크

2776번 암기왕

 

 

적은 범위였다면 배열의 인덱스로 쉽게 구현할 수 있지만

 

정수의 범위가 int이며 개수도 1,000,000개나 되기 때문에 시간초과를 주의해야 하는 문제

해쉬테이블 unordered_map을 사용하여 key, value 쌍으로 값을 저장하고 탐색할 수 있게 사용한다.

단 이것만 가지고는 시간초과가 나기 때문에

ios_base::sync_with_stdio(false);를 통해 C 표준의 동기화를 끊고,

cin.tie(NULL), cout.tie(NULL) 따위로 내부적으로 수행되는 연산을 줄여 시간을 확보한다.

 

 

제출코드

#include <iostream>
#include <unordered_map>

using namespace std;

int T, N, M;

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

	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N;
		unordered_map<int, bool> Map;

		for (int j = 0; j < N; j++)
		{
			int idx = 0;
			cin >> idx;
			Map[idx] = true;
		}

		cin >> M;

		for (int k = 0; k < M; k++)
		{
			int idx = 0;
			cin >> idx;

			if (Map[idx] == 1)
			{
				cout << 1 << "\n";
			}
			else
			{
				cout << 0 << "\n";
			}
		}
	}

	return 0;
}