[종만북] MATCHORDER - 출전 순서 정하기 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-MATCHORDER

 

 

풀이

  생각해야 할 조건은 두 가지이다.

1. 러시아와 한국 팀이 1:1로 매칭이 되긴 해야 한다.

2. 러시아팀의 레이팅 이상이기만 하다면 그 차이는 무시할 수 있다.

 

  위 두가지를 생각하면서 최대한으로 이기려고 한다면, 각 러시아팀 레이팅에 대해 최대한 차이가 적은 그 이상의 한국팀 레이팅을 매칭시켜주면 된다. 또한 1:1로 매칭되긴 해야하므로, 현재 러시아팀 레이팅 이상의 값이 남는게 없다면 남은 한국팀 레이팅 중 가장 낮은 값을 매칭해준다.

 

  현재 러시아의 레이팅 이상이면서 가장 작은 값은 이분 탐색으로 찾도록 구현했다.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine().trim());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        TreeSet<Integer> korean = new TreeSet<>();
        int[] cnt = new int[4001];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            cnt[cur]++;
            korean.add(cur);
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            Integer matching = korean.ceiling(arr[i]);
            if (matching != null) answer++;
            else matching = korean.ceiling(0);

            if (--cnt[matching] == 0)
                korean.remove(matching);
        }

        sb.append(answer).append('\n');
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.