[algospot][MATCHORDER] 출전 순서 정하기

문제 : https://algospot.com/judge/problem/read/MATCHORDER

---

그리디로 풀었다.

한국팀이 지는 경우는 무시하고 이기는 경우만 고려해보자.

한국이 이길 수 있을 때 최대 효율은 가장 적은 레이팅을 가진 선수로 이기는 경우이다. 

따라서 먼저 선수들의 레이팅을 오름차순 정렬했다.

그리고 러시아팀의 레이팅을 앞에서부터 탐색한다.

한국팀 선수의 인덱스 변수(korInd)를 하나 두고 이를 0으로 초기화한다.(한국팀의 레이팅도 앞에서부터 탐색.)

탐색 중인 러시아팀의 레이팅보다 같거나 큰 한국팀 레이팅이 나올 때까지 korInd를 증가시킨다.

찾는 경우 정답 + 1을 하고 korInd는 이미 특정 러시안 선수와 매칭 되었으므로 더이상 사용하지 못한다. 따라서 korInd도 +1해준다.

만약 정답이 가능한 한국팀 레이팅을 찾을 수 없는 경우 앞으로도 러시아팀을 이길 수 없을 것이기 때문에(더이상 정답이 가능한 수가 없다.) 탐색을 종료한다.

이를 모든 러시아팀의 레이팅을 탐색할 때까지 반복한다.

 

시간 복잡도는 레이팅 배열을 정렬하는데 드는 O(NlogN)이다.

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/MATCHORDER.cpp

fpdjsns/Algorithm