백준 2776 암기왕(c++)

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

2776번: 암기왕

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int>v1;
	vector<int>v2;
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		
		for(int i=0;i<n;i++)
		{
			int a;
			cin>>a;
			v1.push_back(a);
		}
		int m;
		cin>>m;
		
		for(int i=0;i<m;i++)
		{
			int b;
			cin>>b;
			v2.push_back(b);
		}
		sort(v1.begin(),v1.end());
		for(int i=0;i<v2.size();i++)
		{
			if(binary_search(v1.begin(),v1.end(),v2[i])) cout<<1<<'\n';
			else cout<<0<<'\n';
		}
		v1.clear();
		v2.clear();
	}
}

<풀이과정>

이 문제는 이분 탐색으로 풀었다. 

정렬된 배열(sort)의 원소가 존재하는지 찾을 수 있는 알고리즘이다. 

검사할 때 마다 계속 탐색범위는 절반씩 줄어든다 

ex) 100개의 원소를 찾을 때, 첫 번째는 100번 검사 .. 두 번째는 50번 검사.

시간 복잡도 : O(log N)

마지막으로 중요한 부분인데, 벡터 배열의 원소들을 제거(clear)해주어야 다음 테스트 케이스에서도 이분탐색 역할을 수행할 수 있다. 벡터의 원소가 존재한다면 이전 케이스에서 진행했던 이분탐색이 같이 진행되기 때문이다.