[백준] 28449: 누가 이길까 - JAVA

https://www.acmicpc.net/problem/28449

 

풀이

HI 팀과 ARC 팀의 모든 사람들끼리 한번씩 대결하여 N X M회의 대결이 성사된다.

 

HI팀이 이기는 횟수, ARC팀이 이기는 횟수, 무승부하는 횟수를 구해야 한다.

 

각 팀의 점수를 입력받아 각각 정렬했다.

 

HI팀을 순회하면서 HI팀원의 점수를 타겟으로 하여 ARC팀에서 해당 점수와 같은 점수가 있는지 찾았다.

 

이때, 이분탐색을 이용하여 같은 점수가 시작되는 지점(drawStart), 같은 점수가 끝나는 지점(drawEnd)를 각각 찾았다.

 

drawStart보다 작은 값들은 HI팀이 이기게 되고, drawEnd보다 큰 값들은 ARC팀이 이기게 된다.

 

---

 

메모리: 41148KB
시간: 700ms
언어: Java 11

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

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

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

        int[] arc = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            arc[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arc);

        long winA = 0;
        long winB = 0;
        long draw = 0;
        for (int i = 0; i < n; i++) {
            int a = hi[i];

            int drawStart = m;
            int drawEnd = -1;

            int left = 0;
            int right = m - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arc[mid] >= a) {
                    drawStart = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            left = Math.max(0, drawStart - 1);
            right = m - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arc[mid] <= a) {
                    drawEnd = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            winA += drawStart;
            winB += (m - drawEnd - 1);
            draw += (drawEnd - drawStart + 1);
        }

        System.out.println(winA + " " + winB + " " + draw);
    }
}