C++ / 백준 / 10815 / 숫자 카드

문제

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

10815번: 숫자 카드

문제풀이

상근이가 가지고 있는 카드 card, 가지고 있는지 확인하는 check 벡터 두 개를 이용한다.

확인하는 카드 수만큼 반복하면서 이분 탐색을 한다.

상근이의 카드들을 정렬시켜야 이분 탐색이 가능하다.

확인 카드를 들고 상근이의 카드 목록을 보면서 이 카드가 있는지를 확인한다.

low와 high를 가지고 가운데인 mid값을 도출하면서

상근이의 카드[mid] < 확인카드이면 low를 mid+1로 변경한다.

상근이의 카드 > 확인카드 high를 mid-1로 변경한다.

확인카드가 더 작은 경우

 

 

확인카드가 더 큰 경우

 

 

코드

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

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

	int N = 0, M = 0;
	int i = 0;

	cin >> N;
	vector<int>card(N, 0);
	for (i = 0; i < N; ++i)
		cin >> card[i];
	sort(card.begin(), card.end());

	cin >> M;

	vector<int>check(M, 0);
	vector<int>answer(M, 0);

	for (i = 0; i < M; ++i) {
		cin >> check[i];
		int low = 0;
		int high = N - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (card[mid] == check[i]) {
				answer[i]++;
				break;
			}
			else if (card[mid] < check[i])
				low = mid + 1;
			else if (card[mid] > check[i])
				high = mid - 1;
		}
	}
	for (i = 0; i < M; ++i)
		cout << answer[i] << " ";
}