[백준/C++] 10815번 : 숫자 카드 (binary_search)

숫자 카드 

문제

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1 

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1 

1 0 0 1 1 0 0 1

---

두 개의 정수 배열을 준 뒤, 하나의 배열 원소들이 다른 배열에 존재하는지를 찾는 문제이다.

 

그러나 숫자의 크기가 -10,000,000 ~ 10,000,000이고, 배열의 총 크기가 500,000 이므로 단순 배열 비교 시에는 제한시간 2초를 넘어가게 된다.

 

따라서 찾고자 하는 배열을 오름차순 정렬(sort)한 뒤, binary_search를 이용해 원소를 찾아보았다.

 

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

using namespace std;

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

	int N;
	cin >> N;
	vector<int> SangCard(N);
	for (int& c : SangCard)
		cin >> c;

	int M;
	cin >> M;
	vector<int> Card(M);
	for (int& c : Card)
		cin >> c;

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

	for(int i = 0; i < M; i++)
		cout << binary_search(SangCard.begin(), SangCard.end(), Card[i]) <<' ';
	return 0;
}

 

binary_search(begin, end, value)

binary_search 함수는 이진탐색을 구현하여 begin~end 범위에서 value를 찾으면 true를, 못찾으면 false를 반환한다.

 

이때, 이진탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 배열이 정렬되어 있어야 한다.

 

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

이진탐색의 시간 복잡도는 O(log N)으로, 배열을 전부 조사하는 find 함수, count 함수인 O(N)에 비해 상대적으로 빠른 탐색 알고리즘에 속한다.

 

아래는 이진 탐색을 직접 구현한 코드이다

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
	int n, data, target, res = -1, lt = 0, rt, mid;
	vector<int> vec;
 
	cin >> n >> target;
 
	for (int i = 0; i < n; i++)
	{
		cin >> data;
		vec.push_back(data);
	}
 
	rt = n - 1;
	sort(vec.begin(), vec.end());
 
	while (lt <= rt)
	{
		mid = (lt + rt) / 2;
 
		if (vec[mid] == target)
		{
			res = mid;
			break;
		}
		else if (vec[mid] > target) rt = mid - 1;
		else if (vec[mid] < target) lt = mid + 1;
	}
 
	cout << "target index : " << res;
}

---

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

10815번: 숫자 카드