[종만북][알고스팟] 출전 순서 정하기 (MATCHORDER) - 그리디(탐욕법) + 이진탐색(BinarySearch) JAVA

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

algospot.com :: MATCHORDER

코드설명

그리디(탐욕법) + 이진탐색(BinarySearch) 을 활용합니다.

 

질 경기라면 가장 레이팅 낮은 선수를 내보내서 지도록 합니다.

이길 수 있는 경기라면, 이길 수 있는 가장 레이팅 낮은 선수를 내보내서 이기도록 합니다.

 

탐욕법의 정당성을 증명하기 위해선, 항상 우리가 하는 선택을 포함하는 최적해가 존재함을 증명해야 합니다.

각 경기에 대해 이 경기를 이길 수 있는 경우, 질 수 밖에 없는경우로 나누어서 우리의 선택이 맞는지, 우리의 선택이 항상 최적해에 포함되는지를 증명해야 합니다.

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int C = Integer.parseInt(st.nextToken());
        while(C-- > 0) {
        	st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	answer = 0;
        	
        	int[] russian = new int[N];
        	ArrayList<Integer> korean = new ArrayList<Integer>();
//            int[] korean = new int[N];
            
            // 러시아팀 선수 레이팅 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                russian[i] = Integer.parseInt(st.nextToken());
            }
            
            // 한국팀 선수 레이팅 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
//                korean[i] = Integer.parseInt(st.nextToken());
                korean.add(Integer.parseInt(st.nextToken()));
            }
            Collections.sort(korean);
            
            for(int rus = 0; rus < N; rus++) {
            	//만약 러시안의 현재 레이팅을 한국 선수가 아무도 못이기는 경우 패배다.
            	//이떄 한국선수의 레코딩 중 가장 작은 한국선수 점수를 준다.
            	if(russian[rus] > korean.get(korean.size() - 1)) {
            		korean.remove(0);
            	}
            	//r
            	else{
            		int koreanIdx = binarySearchLowerBound(korean, 0, korean.size() - 1, russian[rus]);
            		korean.remove(koreanIdx);
            		answer += 1;
            	}
            }
            System.out.println(answer);
        }
        
    }
    
    private static int binarySearchLowerBound(ArrayList<Integer> A, int lo, int hi, int target) {
    	int left = lo - 1;
    	int right = hi + 1;
    	
    	while(left + 1 < right) {
    		int mid = (left + right) / 2;
    		if(A.get(mid) < target) {
    			left = mid;
    		}else if(A.get(mid) >= target){
    			right = mid;
    		}
    	}
    	return right;
    }
    
    
}