백준 1920번 "수찾기" [Hash의 Rehash 과정의 문제]

문제

 

 

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------

 

문제 접근 순서.

 

1. 어떠한 원소를 찾아야 하는 문제이므로 hash 자료형을 이용할 생각. 

 

2. hash에서 rehash(재해싱)에 관한 문제가 생길수 있으므로 반드시 미리 공간을 확보한 다음 

    사용하기 ( 안할 시  N=100000 기준 으로 O(N) 리해싱 복잡도가 14번 나오므로 시간 초과를 유발함) 

 

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------

 

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std; 

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

	int i_inputCount; 
	unordered_set<int> m_set; 

	cin >> i_inputCount; 
	m_set.reserve(i_inputCount);


	for(int i=0; i<i_inputCount; i++)
	{
		int iNumber; 
		cin >> iNumber;
		m_set.emplace(iNumber);
	}

	int i_FindCase;
	cin >> i_FindCase; 

	for(int i=0; i<i_FindCase; i++)
	{
		int i_FindNumber;
		cin >> i_FindNumber; 

		if(m_set.find(i_FindNumber)!= m_set.end())
		{
			cout << "1" << "\n";
		}

		else
			cout << "0" << "\n";
	}
	
}