[백준] 1920 수찾기 (C++)

백준 1920 수찾기 문제
백준 1920 수찾기 소스코드

📄 문제 설명

Problem

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

Input

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

Output

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

Example Input

5
4 1 5 2 3
5
1 3 7 9 5

Example Output

1
1
0
0
1

📝 문제 해설

N개의 정수 배열(data)에
      ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
data  | 4 | 1 | 5 | 2 | 3 |
      ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 

M개의 정수 배열(comp)의 각 원소가 존재한다면 1을 존재하지 않다면 0을 출력하는 문제.
      ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
comp  | 1 | 3 | 7 | 9 | 5 |
      ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

간단하게 이중 반복문으로도 작동하게 코드를 짤 수 있지만,
N과 M의 크기가 최대 100,000이기 때문에 시간복잡도가 O(NM) ≒ O(N²)으로 Time Out 우려가 있다.

탐색 방법 중 이분 탐색(Binart Search)을 이용해 문제를 푼다면,
시간 복잡도가 O(Mlog_2 N) ≒ O(Nlog N) 안에 해결이 가능하다.

⚠⚠ 이분탐색 전에 탐색하려는 배열은 꼭 정렬이 되어 있어야한다.

</> Source Code

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, m;
	vector<int> data;
	vector<int> comp;

	scanf("%d", &n);
	
	for(int j = 0; j < n; j++){ // N개의 정수 입력
		int x;
		scanf("%d", &x);
		data.push_back(x);
	}
	
	scanf("%d", &m);
	
	for(int j = 0; j < m; j++){ // M개의 정수 입력
		int x;
		scanf("%d", &x);
		comp.push_back(x);
	}
	
	sort(data.begin(), data.end()); // (N개의 정수 벡터) data 정렬
	
	for(int i = 0; i < m; i++){
		bool exist = false; // 존재 확인을 위한 flag
		
		//binary search (이분 탐색)
		int left = 0;
		int right = n;
			
		while(left <= right){
			int mid = (left + right) / 2;
			
			if(data[mid] == comp[i]){
				exist = true;
				break;
			}
			else if(data[mid] > comp[i]){
				right = mid - 1;
			}
			else{
				left = mid + 1;
			}
		}
		
		if(exist){
			printf("1\n");
		}
		else{
			printf("0\n");
		}
	}
	return 0;
}