문제


입출력


문제 요약

6 3 2 10 -10

 

이렇게 입력 값이 주어진다면

 

10 9 -5 2 3 4 5 -10

위 배열이 입력 값에 포함된다면 1출력 아니면 0을 출력하면 된다.

 

단순하게 2중 반복문으로 탐색을 할 순 있지만

 

카드의 수가 500,000개로 (n)^2이면 시간제한에 넘기 때문에 이진 탐색으로 풀어야한다는 걸 알 수 있다.

 

1. 이진 탐색은 정렬이 필수적으로 필요하기 때문에 입력 배열을 정렬한다.

-10 2 3 6 10

이 배열을 갖고 입력값마다 존재한지 아닌지를 판단해주면 된다.


코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int N, M, temp;
	vector<int> v1;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> temp;
		v1.push_back(temp);
	}

	sort(v1.begin(), v1.end());
	
	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> temp;
		cout << binary_search(v1.begin(), v1.end(), temp) << " ";
	}


	return 0;

}