7795번 . 먹을 것인가 _ lower_bound

첫번째 풀이

: 아무 생각없이 풀었음.
-> 역시 시간복잡도 m n 이 나옴.
: 2만 2만...

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


int main() 
{
	int t;
	cin >> t;

	for (int i = 0; i < t; ++i)
	{
		int n, m;

		cin >> n >> m;
		vector<int>v(n);

		for (int i = 0; i < n; ++i)
			cin >> v[i];

		vector<int>v2(m);

		for (int i = 0; i < m; ++i)
			cin >> v2[i];
		// v의 원소가 v2의 원소보다 커야 카운팅함.


		// 1 1 3 7 8
		// 1 3 6 
		int cnt = 0;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (v[i] > v2[j])
					++cnt;
			}
		}

		cout << cnt << endl;

	}

}

-> 오름차순으로 정렬한 다음에 어떻게 할것인가 를 생각해봄...
문제를 생각해보면.
1 1 3 7 8 vs 1 3 6

비교를 하게 되는데,,,
8 친구는 1, 3, 6 -> 보다 큼. : cnt +=3
7 친구는 1, ,3 ,6 보다는 큼 : cnt += 3
3 친구는 1보다 큼. cnt += 1
1 친구보다 작은 친구가 없음...
=> stl의 lower_bound를 사용하면 됨.

두번째 풀이

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>




int main() 
{
	int t;
	cin >> t;

	for (int i = 0; i < t; ++i)
	{
		int n, m;

		cin >> n >> m;
		vector<int>v(n);

		for (int i = 0; i < n; ++i)
			cin >> v[i];

		vector<int>v2(m);

		for (int i = 0; i < m; ++i)
			cin >> v2[i];
		// v의 원소가 v2의 원소보다 커야 카운팅함.

		sort(v.begin(), v.end());
		sort(v2.begin(), v2.end());

		int cnt = 0;
		for (int i = 0; i < n; ++i)
		{
			// 1 1 3 7 8
			// 1 3 6

			auto iter = lower_bound(v2.begin(), v2.end(), v[i]);
			cnt += iter - v2.begin();
		
		}

		cout << cnt << endl;

	}
}