출전 선수 정하기 - Greedy

무식하게 풀 수 없을까? 한국 선수들의 순열을 만들어 러시아 선수들과 매칭 시킨다면 n!의 경우의 수가 발생하므로 시간 초과가 발생한다.

 

그럼 러시아팀을 상대로 최다승을 할 한국 선수들을 탐욕적으로 선택할 수는 없을까? → 남은 선수 중 상대방 선수를 한명이라도 이길 수 없는 선수가 있다면 가장 레이팅이 높은 러시아 선수와 매칭시킨다. 남은 선수 중 상대방 선수를 이길 수 있는 선수들이 있다면 그 선수들 중 가장 레이팅이 낮은 선수를 매칭시킨다.

import java.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int testCase = Integer.parseInt(br.readLine());

        for(int t=0; t<testCase; t++) {
            int N = Integer.parseInt(br.readLine());

            int[] russia = new int[N];
            int[] korea = new int[N];

            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<N; i++) russia[i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<N; i++) korea[i] = Integer.parseInt(st.nextToken());

            Arrays.sort(russia);
            Arrays.sort(korea);

            int answer = 0;
            int russia_idx = 0;
            for(int i=0; i<korea.length; i++) {
                if(korea[i] >= russia[russia_idx]) {
                    answer++;
                    russia_idx++;
                }
            }
            System.out.println(answer);
        }
    }
}