알고스팟: 출전 순서 정하기 (ID: MATCHORDER)

[문제 링크]

algospot.com :: MATCHORDER

---

간단한 그리디 알고리즘 문제였다.

러시아팀의 한 선수를 이길 수 있는 한국팀의 선수가 여러명 있을 때 가장 레이팅이 낮은 선수를 매칭시켜야만 최대의 승점을 얻을 수 있기 때문에 이를 그대로 구현하였다.

 

먼저 러시아팀, 한국팀의 선수들을 레이팅에 따라 오름차순으로 정렬한다.

러시아팀에서 레이팅이 가장 낮은 선수를 시작으로 한국팀에서 레이팅이 가장 낮은 선수부터 비교한다.

한국팀 선수가 러시아팀 선수보다 레이팅이 같거나 클경우 두 선수를 매치 시키고 러시아팀의 다음 선수를 비교한다.

한국팀에서 가장 레이팅이 높은 선수까지 탐색했다면 더이상 비교할 필요가 없기 때문에 누적한 승점을 반환한다.

---

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

vector<int> rusia, korea;

int Greedy(int N)
{
	// 오름차순 정렬
	sort(rusia.begin(), rusia.end());
	sort(korea.begin(), korea.end());

	int lowest = 0, win = 0;

	for (int i = 0; i < N; i++)
		if (rusia[lowest] <= korea[i])
		{
			lowest++;
			win++;
		}

	return win;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int N;
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			rusia.push_back(rate);
		}

		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			korea.push_back(rate);
		}

		cout << Greedy(N) << endl;

		rusia.clear();
		korea.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 107 day