[백준/C++] 7795번 : 먹을 것인가 먹힐 것인가

먹을 것인가 먹힐 것인가

---

아이디어

오름차순으로 정렬해서 key에 대한 하한을 찾아주면 된다.
이분탐색으로 구현을 했는데 [mid]의 값이 key보다 작으면 [mid]는 key의 입장에서 먹을 수 없는 것이기 때문에 오른쪽 부분은 전부 못먹는 것으로 분류하고 high의 범위를 mid-1로 조정한다.
low의 범위도 마찬가지

입력#1

5 3
1 1 3 7 8
1 3 6

key = 7인 경우

1. low = 0, high = 2, mid = 1
   else if (7 > 3)
   low = 2

2. low = 2, high = 2, mid = 2
   else if (7 > 6)
   low = 3

3. low = 3, high = 2
   count += low;

입력#2

3
5 5
1 1 3 7 8
1 3 6 6 6
5 5
1 1 1 1 1
1 1 1 1 1
3 5
1 2 3
1 2 3 4 5

출력은 11 0 3이 나온다.

---

제출 코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int* arrN;
int* arrM;
int count = 0;

void Find(int key)
{
	int mid;
	int low = 0, high = m - 1;

	while (low <= high)
	{
		mid = low + (high - low) / 2;

		if (key <= arrM[mid]) // arrM[mid]는 먹을 수 없는 것
			high = mid - 1;
		else if (key > arrM[mid])
			low = mid + 1;
	}

	::count += low;
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t, count = 0;
	cin >> t;
	int* result = new int[t];

	for (int i = 0; i < t; i++)
	{
		cin >> n >> m;
		arrN = new int[n];
		arrM = new int[m];

		for (int j = 0; j < n; j++)
			cin >> arrN[j];

		for (int k = 0; k < m; k++)
			cin >> arrM[k];

		sort(arrN, arrN + n);
		sort(arrM, arrM + m);

		for (int l = 0; l < n; l++)
			Find(arrN[l]);

		result[i] = ::count;
		::count = 0;
	}

	for (int i = 0; i < t; i++)
		cout << result[i] << '\n';

	return 0;
}

제출코드의 시간복잡도는 O(nlogn)이다.