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

숫자 카드 2

---

아이디어

-10 -10 2 3 3 / 6 7 10 10 10

정렬을 하면 특정 숫자가 어느 특정 지역에 몰려있음을 볼 수 있다.
그 숫자의 개수를 알고 싶으면 상한과 하한을 빼면 된다.

하한 : 찾고자 하는 값 이상의 값이 처음 나타나는 위치
상한 : 찾고자 하는 값을 초과하는 값이 처음 나타나는 위치

Lower(3, 10)

1. left = 0, right = 10, mid = 5
   if(3 <= 6)
   right = 5
   

2. left = 0, right = 5, mid = 2
   else // 3 > 2
   left = 3

3. left = 3, right = 5, mid = 4
   if(3 <= 3)
   right = 4

4. left = 3, right = 4, mid = 3
   if(3 <= 3)
   right = 3
   

5. return 3;

Higher(3, 10)

1. left = 0, right= = 10, mid = 5
   if(3 <= 6)
   right = 5
   
2. left = 0, right = 5, mid = 2
   else // 3 > 2
   left = 3
   
3. left = 3, right = 5, mid = 4
   else // 3 < 3
   left = 5
   
4. return 5;

추가 지식

• mid를 구할때 (left + right) / 2를 하지 않은 이유는 left = 20억이고, right = 21억인 경우 오버플로우가 일어나 정상적인 결과가 나오지 않기 때문이다.

---

제출 코드

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int N[500000];
int M[500000];

int Lower(int target, int size)
{
	int mid;
	int left = 0;
	int right = size;

	while (left < right)
	{
		mid = left + (right - left) / 2;

		if (target <= N[mid])
			right = mid;
		else
			left = mid + 1;
	}
	return left;
}

int Higher(int target, int size)
{
	int mid;
	int left = 0;
	int right = size;

	while (left < right)
	{
		mid = left + (right - left) / 2;
		if (target < N[mid])
			right = mid;
		else
			left = mid + 1;
	}
	return left;
}

int main(int argc, char* argv[]) {

	int num, mum;

	scanf("%d", &num);

	for (int i = 0; i < num; i++)
		scanf("%d", &N[i]);

	sort(N, N + num);

	scanf("%d", &mum);

	for (int i = 0; i < mum; i++)
		scanf("%d", &M[i]);

	int* result = new int[mum];

	for (int i = 0; i < mum; i++)
	{
		int lower = Lower(M[i], num);
		int higher = Higher(M[i], num);
		result[i] = higher - lower;
		printf("%d ", result[i]);
	}

	return 0;
}