[백준 C++] 10815 : 숫자 카드

https://www.acmicpc.net/problem/10815

브루트포스 방식으로 모든 숫자 카드들을 비교하면 시간 초과로 해결하지 못하는 문제이다.

시간 단축을 위해 이분 탐색을 활용해 숫자 카드들을 비교할 것이다.

---

이분탐색은 한 리스트에 있는 데이터들의 탐색 범위를 점점 좁혀나가면서 구분하는 방식이다.

시작 노드 및 끝노드 인덱스를 더한 뒤 2로 나누어 중간 인덱스를 구하고,  그 값과 원하는 타겟값을 비교해서 targer > list[mid]인 경우 시작 노드값을 올리고, 반대인 경우는 끝 노드의 값을 올려가면서 찾는다.

이 이분 탐색은 반복문(while)을 사용한 방법과 재귀를 사용한 방법, 두 가지가 존재하는데 필자는 재귀를 좋아하기 때문에 재귀 방식을 사용하였다.

 

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

using namespace std;

vector<int> own;
vector<int> compare;
int N, M;

int check(int target, int start, int end)
{
	if (start > end)
		return 0;

	int mid = (start + end) / 2;

	if (target == own.at(mid))
		return 1;
	else if (target > own.at(mid))
		return check(target, mid + 1, end);
	else
		return check(target, start, mid - 1);
}

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

	int temp;

	cin >> N;

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

	cin >> M;

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

	sort(own.begin(), own.end());

	for (int i = 0; i < M; i++)
	{
		cout << check(compare.at(i), 0, N - 1) << " ";
	}

	return 0;
}