[백준] 10815번: 숫자 카드 / C++ / 이분탐색

풀이 문제 : 백준 10815번 숫자카드
풀이 언어 : C++
알고리즘 : 이분탐색
문제링크 : https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

문제요약

---

상근이가 가지고 있는 숫자 카드 배열 N과, 다른 숫자카드 M을 받고 M배열에 상근이의 숫자카드 N이 존재하는 지 확인하는 문제다.
1920번 문제와 매우 유사하므로 이번 문제가 어려웠다면 1920번 문제를 풀어보는 것을 권한다.

[백준] 1920번: 수 찾기 / C++ / 이분탐색

 

접근 방식

---

1. 숫자카드의 개수가 최대 500,000개로, 2중 for문 이용시 시간 제한 2초가 초과되기 때문에 이분탐색을 이용해야한다.

2. 숫자 카드에 적혀있는 수의 범위가 -10,000,000 ~ 10,000,000 으로, mid 값을 구하기 위해 더한다고 해도, int 범위 내에서 이루어 질 수 있다. (int 범위 : -2,147,483,648 ~ 2,147,483,647) 그러므로 int 형을 이용한다.

 

코드

---

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

int n, m;
int an[500001];
int am[500001];

void bs(int in) {
	int left = 0;
	int right = n - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (an[mid] == in) {
			cout << 1;
			return;
		}
		else if (an[mid] > in) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout << 0;
	return;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> an[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> am[i];
	}

	sort(an, an + n);

	for (int i = 0; i < m; i++) {
		bs(am[i]);
		cout << ' ';
	}
	
	return 0;
}