[C++] 백준 10816번 숫자 카드 2

 

1) 문제설명

백준 Online Judge 10816번 숫자 카드 2

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

10816번: 숫자 카드 2

 

2) 아이디어

이분 탐색을 이용하여 배열 안의 키 값을 찾는다.

단 겹치는 숫자카드의 개수를 세어야 하므로 이분 탐색을 실행하면서 찾고자 하는 키값들 중 배열의 맨 처음 인덱스와 마지막 인덱스의 차이를 출력한다면 그 키값이 배열 안에 몇 개 있는지 알 수 있으므로 이를 이용한다.

up_binary_search : 배열 안의 키값의 맨 마지막 인덱스를 리턴

low_binary_search : 배열안의 키값의 맨 처음 인덱스를 리턴

두 개를 뺀 뒤 출력한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[10000001];

int up_binary_search(int start, int end, int key) {
	if (start == end) {
		return start;
	}
	int mid = (start + end) / 2;
	if (key < arr[mid]) {
		return up_binary_search(start, mid, key);
	}
	else {
		return up_binary_search(mid + 1, end, key);
	}
}
int low_binary_search(int start, int end, int key) {
	if (start == end) {
		return start;
	}
	int mid = (start + end) / 2;
	if (key <= arr[mid]) {
		return low_binary_search(start, mid, key);
	}
	else {
		return low_binary_search(mid + 1, end, key);
	}
}

int main() {
	int n,m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + n);
	cin >> m;
	for (int i = 0; i < m; i++) {
		int k;
		scanf("%d", &k);
		printf("%d ", up_binary_search(0, n, k) - low_binary_search(0, n, k));
	}
}