[BaekJoon] 2461 대표 선수 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static PriorityQueue<Integer>[] students; // 각 반의 능력치를 오름차순으로 담기 위해 PriorityQueue 이용

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        students = new PriorityQueue[N];
        for(int idx = 0; idx < N; idx++)
            students[idx] = new PriorityQueue<>();

        for(int idx = 0; idx < N; idx++) {
            for(int num = 0; num < M; num++)
                students[idx].offer(scanner.nextInt());
        }
    }

    static void solution() {
        // PriorityQueue에 각 학급에서 능력치가 가장 낮은 학생의 능력치 및 학급 번호를 저장
        PriorityQueue<Student> minStudents = new PriorityQueue<>();
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        // 각 학급에서 능력치가 가장 낮은 학생들의 능력치 중 최댓값 및 최솟값 찾기
        for(int idx = 0; idx < N; idx++) {
            int ability = students[idx].poll();

            min = Math.min(min, ability);
            max = Math.max(max, ability);

            minStudents.offer(new Student(idx, ability));
        }

        int minDiff = max - min; // 초기 차이값
        while(true) {
            // 만약 능력치가 가장 낮은 학생이 속한 학급에 더이상 학생이 없다면 반복문 종료
            if(students[minStudents.peek().idx].isEmpty()) break;

            // 능력치가 가장 낮은 학생을 뽑아내고 해당 학생의 학급에서 다음으로 가장 낮은 능력치를 가진 학생 뽑기
            Student ability = minStudents.poll();
            int abilityNum = students[ability.idx].poll();

            // 뽑은 그 학생의 능력치가 현재 abilities에 존재하는 학생들의 능력치의 최댓값보다 크다면
            // 그 값으로 최댓값 갱신
            max = Math.max(max, abilityNum);

            // 뽑은 학생을 abilities에 추가
            minStudents.offer(new Student(ability.idx, abilityNum));
            // 최댓값은 이전에 갱신했으니 최댓값과 최솟값의 차이를 구하고 이것이 현재까지 구한 차이보다 작다면
            // 이 값으로 갱신
            minDiff = Math.min(minDiff, max - minStudents.peek().ability);
        }

        System.out.println(minDiff);
    }

    static class Student implements Comparable<Student> {
        int idx, ability;

        public Student(int idx, int ability) {
            this.idx = idx;
            this.ability = ability;
        }

        @Override
        public int compareTo(Student o) {
            if(ability != o.ability) return ability - o.ability;
            return idx - o.idx;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}