소유하는 카드를 입력받은후에
입력으로 들어오는 카드를 가지고 있는지 검사하여 가지고 있으면 1, 아니면 0을 출력하는 프로그램을 작성하라
Solution
단순한 이분탐색 문제이다.
이분탐색은 정렬되어있어야하기에 입력을 받은후 정렬을 한다음, 이분탐색으로 각각의 케이스에 대한 답을 도출해준다.
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
cin >> m;
while (m--) {
int goal;
cin >> goal;
int left = 0;
int right = n - 1;
bool state = false;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == goal) {
state = true;
break;
}
if (a[mid] > goal) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
if (state) cout << 1 << ' ';
else cout << 0 << ' ';
}
return 0;
}
참고 : https://code.plus/course/43 , 분할 정복