백준 10816 - 숫자카드2

수정 전

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> arr;
vector<int> keys;

int test(int low, int height, int key) {
	int mid = (low + height) / 2;

	if (arr[mid] == key) {
		int index = mid;
		int count = 1;
		while (!(index <= 0 || index == arr.size() - 1)) {
			index--;
			if (arr[index] == key)
				count++;
			else {
				break;
			}
		}
		index = mid;
		while (!(index <= 0 || index == arr.size() -1)) {
			index++;
			if (arr[index] == key)
				count++;
			else {
				break;
			}
		}
		return count;
	}
	if (mid == low || mid == height)
		return 0;
	

	if (arr[mid] > key) {
		return test(low, mid, key);
	}
	if (arr[mid] < key) {
		return test(mid, height, key);
	}
	
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int key;
		scanf("%d", &key);
		arr.push_back(key);
	}
	sort(arr.begin(), arr.end());
	cin >> M;
	for (int i = 0; i < M; i++) {
		int key;
		scanf("%d", &key);
		keys.push_back(key);
	}
	for (int i = 0; i < keys.size(); i++) {
		printf("%d ", test(0, keys.size(), keys[i]));
	}
	return 0;
}

 수정 후

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> arr;
vector<int> keys;

int LowerBinary(int key) {
	int mid, start, end;
	start = 0;
	end = arr.size() - 1;

	while (end > start) {
		mid = (start + end) / 2;
		// key가 시작하는 곳 찾기
		// 배열이 key보다 크거나 같을경우 end 범위 줄이기
		if (arr[mid] >= key) {
			end = mid;
		}
		else {
			// start = mid 로하면 안끝남
			start = mid + 1;
		}
	}
	return end;
}
int UpperBinary(int key) {
	int mid, start, end;
	start = 0;
	end = arr.size() - 1;

	while (end > start) {
		mid = (start + end) / 2;
		// key의 끝부분 찾기
		// 배열 값이 key 값보다 큰 곳으로 가기
		if (arr[mid] > key) {
			end = mid;
		}
		else {
			// start = mid 로하면 안끝남
			start = mid + 1;
		}
	}
	return end;
}
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int key;
		scanf("%d", &key);
		arr.push_back(key);
	}
	sort(arr.begin(), arr.end());
	cin >> M;
	for (int i = 0; i < M; i++) {
		int key;
		scanf("%d", &key);
		keys.push_back(key);
	}
	for (int i = 0; i < keys.size(); i++) {
		int lower = LowerBinary(keys[i]);
		int upper = UpperBinary(keys[i]);
		if (upper == arr.size() - 1 && arr[arr.size() - 1] == keys[i])
			upper++;
		printf("%d ", upper - lower);
	}
	return 0;
}