(c++)백준 10816번: 숫자 카드 2

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

10816번: 숫자 카드 2

[풀이]

10815번 숫자 카드와는 다르게 상근이가 해당 숫자 카드를 몇 개 가지고 있는지 확인하는 문제였다. 

기본 이분탐색으로는 카드의 유무만 판단할 수 있기 때문에 upperbound와 lowerbound를 구하는 방식을 사용했다. 

upperbound는 찾으려는 값보다 큰 값이 처음 나오는 위치이고, lowerbound는 찾으려는 값 이상인 값이 처음 나오는 위치이다.

 

#include <iostream>
#include <algorithm>//sort
using namespace std;
#define Max 500001

int N, M;
int SNum[Max];//상근이가 가지고 있는 숫자 카드들

//찾으려는 값 이상의 수가 처음 나오는 위치 찾기
int LowerBound(int card) {
	int mid, low, high;
	low = 0;
	high = N - 1;

	while (low < high) {
		mid = (low + high) / 2;
		if (SNum[mid] >= card)
			high = mid;
		else
			low = mid + 1;
	}
	return high;
}

//찾으려는 값보다 큰 수가 처음 나오는 위치 찾기
int UpperBound(int card) {
	int mid, low, high;
	low = 0;
	high = N - 1;

	while (low < high) {
		mid = (low + high) / 2;
		if (SNum[mid] > card)
			high = mid;
		else
			low = mid + 1;
	}
	return high;
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> SNum[i];
	}
	sort(SNum, SNum + N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		int card;
		cin >> card;
		
		int lower = LowerBound(card);
		int upper = UpperBound(card);

		if (upper == N - 1 && card == SNum[N - 1])
			upper++;
		cout << upper - lower << ' ';
	}
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	solution();
	return 0;
}