본문 바로가기
Study/알고리즘 문제해결전략(종만북)

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

by Nahwasa 2023. 4. 17.

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

목차

    문제 : 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');
        }
    }

     

     

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

     

    댓글