[백준/10816] 숫자 카드 2 (이분 탐색)

1. 문제

 

 

 

2. 접근 방법

이분 탐색 알고리즘으로 접근하되, 찾고자 하는 숫자가 시작하는 지점, 끝나는 지점을 찾아야 한다.

즉, 변형된 이분 탐색 알고리즘이라고 생각하면 된다.

찾고자 하는 숫자 이상의 값이 처음으로 시작하는 지점은 Lower Bound 라 하고,

찾고자 하는 숫자 초과의 값이 처음으로 시작하는 지점은 Upper Bound 라고 한다.

우리의 목표는 Lower Bound와 Upper Bound를 구하고, 두 지점의 차이만큼을 구해

가지고 있는 카드의 숫자를 구하는 것이다.

 

입력이 6, 3, 2, 10, 10, 10, -10, -10, 7, 3 이라고 했을 때, 우선 이분 탐색을 위해 정렬시킨다.

그럼 -10, -10, 2, 3, 3, 6, 7, 10, 10, 10 과 같이 정렬된다. 여기에서 이분 탐색을 시작한다.

 

먼저 Lower Bound를 구하는 방법을 알아보자. 다음과 같은 순서로 진행하면 된다.

 

(1) 이분 탐색의 알고리즘과 비슷하게 진행하되, Mid 인덱스와 찾는 값이 일치했을 때 종료하지 않고,

    Last 인덱스를 Mid 인덱스보다 1 작은 값으로 설정하여, 범위를 좁혀준다.

(2) 이분 탐색의 종료 시점은 동일하게 First 값이 Last 값보다 커졌을 때이다.

    여기에서는 종료되었을 때의 First 값이 Lower Bound가 된다.

 

위의 알고리즘대로 카드 '3'을 찾으면 다음과 같은 순서로 진행된다.

 

 

즉, 마지막에 First 인덱스가 위치한 3번이 Lower Bound가 되는 것이다.

 

 

같은 방법으로, Upper Bound를 찾는 방법을 알아보자.

 

(1) 이분 탐색의 알고리즘과 비슷하게 진행하되, Mid 인덱스와 찾는 값이 일치했을 때 종료하지 않고,

    First 인덱스를 Mid 인덱스보다 1 큰 값으로 설정하여, 범위를 좁혀준다.

(2) 이분 탐색의 종료 시점은 동일하게 First 값이 Last 값보다 커졌을 때이다.

    여기에서는 종료되었을 때의 Last 값이 Upper Bound가 된다.

 

카드 '3'에 대한 Upper Bound를 계산해보자.

 

 

위와 같이 진행되고, Last 인덱스가 위치한 4번이 Upper Bound 이다.

원래대로라면, Upper Bound에서 계산된 값 + 1을 해야 진정한 Upper Bound 이지만,

우리는 계산의 편의를 위해 'l' 의 값을 그대로 리턴해서 사용하겠다.

 

즉, 위의 알고리즘을 통해 카드 '3'을 갖고 있는 개수는 Upper Bound(3) - Lower Bound(3) + 1 임을 알 수 있다.

 

 

 

3. 구현

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int cards[500000];

int lowerBound(int n)
{
	int f = 0, l = N - 1, m;
	for (;;)
	{
		m = (f + l) / 2;

		if (f > l)
		{
			if (cards[f] == n) return f;
			else return -1;
		}

		if (cards[m] >= n) l = m - 1;
		else f = m + 1;
	}
}

int upperBound(int n)
{
	int f = 0, l = N - 1, m;
	for (;;)
	{
		m = (f + l) / 2;

		if (f > l)
		{
			if (cards[l] == n) return l;
			else return -1;
		}

		if (cards[m] <= n) f = m + 1;
		else l = m - 1;
	}
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> cards[i];
	sort(cards, cards + N);

	cin >> M;
	int n, res;
	for (int i = 0; i < M; i++)
	{
		cin >> n;
		res = upperBound(n);
		if (res == -1) cout << "0 ";
		else cout << res - lowerBound(n) + 1 << " ";
	}

	return 0;
}