백준(BOJ) 10815번: 숫자 카드

문제링크:   https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

입력: 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 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을 공백으로 구분해 출력한다.

 

나의 풀이:
이분 탐색 이용

 

주의할점?

비교할 수가 많기에 선형탐색은 시간안에 불가능하니 이분탐색을 해야 했다. 

이분탐색을 하려면 내가 가진 카드를 먼저 오름차순으로 정렬해야 한다.

 

코드( C++ )

 

#include  <iostream>
#include  <vector>
#include  <algorithm>
using namespace std;
vector mycard;
vector doyouhavecard;
int N;
bool CompareCard(int num, int lo, int hi) //이분 탐색으로 비교해본다.
{
int mid;
while (lo <= hi) {
mid = (lo + hi) / 2;
if (mycard[mid] == num)
return true;
if (mycard[mid] < num)
lo = mid + 1;
else if (mycard[mid] > num)
hi = mid - 1;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; ++i)
{
int num;
cin >>  num;
mycard.push_back(num); // 카드를 넣어준다
}
sort(mycard.begin(), mycard.end()); // 이분탐색을 쓰도록 카드를 오름차순으로 정렬한다.
int cnum;
cin >> cnum;
for (int i = 0; i < cnum; ++i)
{
int num;
cin >> num;
if (CompareCard(num, 0, mycard.size() - 1)) // true라면 1을 집어넣는다.
{
doyouhavecard.push_back(1);
}
else
doyouhavecard.push_back(0);
}
for (int i = 0; i < doyouhavecard.size(); ++i)
{
cout << doyouhavecard[i] << " ";
}
return 0;
}