C++ 백준 10815번

백준 10815번 www.acmicpc.net/problem/10815

10815번: 숫자 카드

문제 : 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

이 문제를 풀기 전에 이분 탐색(Binary Search)에 대해서 짧게 설명을 하자면

그냥 쉽게 생각해서 반으로 잘라서 그 반보다 같냐/크냐/작냐를 가리고 또 그 반을 잘라서 같냐/크냐/작냐를 가리는 것이다.

그러니까 약간 그 소주 뚜껑에 적힌 숫자 찾는?!?!? 술 게임(나만 해봤나?!?!)을 예로 들면 찾아야 되는 수가 78이고

숫자가 1~99까지 있다고 가정해보자!!

 

당연히 처음엔 50을 부를 거고 78은 50보다 크니까 up이라고 하면 그다음에는 50~99 사이 수인 75를 부를 거고 78은 75보다 크니까 또 up, 그다음은 75와 99 사이인 87을 부르고... 이렇게 하다 보면 결국 78을 찾을 수 있다.

이분 탐색이 그냥 이렇게 반으로 잘라서 탐색하는 것이다.

 

그래서 이 문제를 풀 때 이분 탐색을 사용하면 된다!!

 

숫자가 8개 있으면 처음에는 제일 왼쪽(left)이 0, 제일 오른쪽(right)이 7이고(인덱스가)

여기서 반(mid)인 인덱스 4를 기준으로 이 숫자가 내가 원하는 숫자보다 큰지 작은 지를 찾을 수 있는데 만약 크다면 4보다 더 큰 수에서 찾아야 되고 그거보다 작은 친구들은 그냥 다 버리면 되니까 right는 그대로 두고 left = mid + 1로 바꾸고 작다면 left는 그대로 두고 right = mid - 1로 바꾸면 된다. 그래서 이렇게 반복하다 보면 숫자를 찾을 수 있다.

이 과정이 끝났는데 숫자를 못 찾으면 이건 그냥 없는 숫자인 것이다.

그리고 이분 탐색할 때 숫자는 정렬돼있어야 된다!!! 당연히 반으로 나눠서 크고 작고를 가리려면 정렬이 되어있어야 함!!

 

#include<iostream>
#include<algorithm>
using namespace std;
int a[500001];
int b[500001];
int c[500001] = { 0, }; // 정답 저장 배열
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	sort(a, a + n); // 오름차순으로 정렬
	for (int i = 0; i < m; i++) {
		int right = n - 1; // 제일 오른쪽(맨 뒤) 인덱스
		int left = 0; // 제일 왼쪽(맨 앞) 인덱스
		while (left <= right) {
			int mid = (right + left) / 2;
			if (a[mid] == b[i]) {
				c[i] = 1;
				break;
			}
			if (a[mid] > b[i]) {
				right = mid - 1;
			}
			else {
				left = mid + 1;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		cout << c[i] << ' ';
	}
	cout << '\n';
}