(백준 c++)1920 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

 

정수의 범위가 상당히 크다.

그렇기 때문에 계수 정렬이나 find 알고리즘을 사용하면 시간이 초과될 것이다.

N개의 수를 벡터에 입력받은 후 오름차순으로 정렬하여 이분탐색을 통해 탐색을 해야한다.

 

이분탐색의 형식은 front, back, mid를 이용한다.

front는 맨 앞, back은 맨 뒤, mid는 front와 back의 중간값이다.

중간값을 구해 v[mid]가 구하려는 수(m)인지 확인한다.

 

만약 m < v[mid]면 back 값을 -1 해주어 범위를 앞쪽으로 좁힌다.

m > v[mid]면 front 값을 -1 해주어 범위를 뒤쪽으로 좁힌다.

 

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

using namespace std;

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

	int N, M;

	cin >> N;

	vector<int> v(N);

	for(int i = 0; i < N; i++){
		cin >> v[i];
	}
	
	sort(v.begin(), v.end());

	cin >> M;

	for(int i = 0; i < M; i++){
		int m;
		int front = 0;
		int back = v.size();
		bool check = false;

		cin >> m;

		while(front <= back){
			int mid = (front + back) / 2;
			
			if(v[mid] == m){
				check = true;
				break;
			}

			if(m < v[mid]){
				back = mid - 1;
			}
			else{
				front = mid + 1;
			}
		}

		if(check){
			cout << 1 << "\n";
		}
		else{
			cout << 0 << "\n";
		}
	}
}