백준 2461번 대표 선수 (JAVA)

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

2461번: 대표 선수

 

저는 정렬과 우선순위 큐를 통해 문제를 해결했습니다.

먼저 학급마다 오름차순으로 정렬하고 맨 앞의 값을 우선순위큐에 넣었습니다.

우선순위큐는 값이 가장 낮은 값을 맨 앞으로 오도록 하였습니다.

우선순위큐에서 맨 앞에 있은 값을 빼서 해당 학급의 다음 학생을 다시 우선순위 큐에 넣습니다.

그리고 우선순위큐에서 값이 가장 큰 값을 계속 추적해 나가면서 우선순위 큐의 맨 앞과 비교해 차이가 가장 작은 값을 찾았습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_2461 {
    private static final int MAX = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[][] input = new int[n][m];
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < m ; j++){
                input[i][j] = stoi.apply(st.nextToken());
            }
            Arrays.sort(input[i]);
        }
        int result = MAX;
        PriorityQueue<int[]> pq = new PriorityQueue<>((v1,v2)->{
            return v1[0] - v2[0];
        });
        int max = 0;
        for(int i = 0 ; i < n ; i++){
            pq.offer(new int[]{input[i][0],i,0});
            max = Math.max(input[i][0],max);
        }
        while(true){
            result = Math.min(max-pq.peek()[0],result);
            int[] now = pq.poll();
            int i = now[1];
            int j = now[2];
            j++;
            if(j >= m){
                break;
            }
            int value = input[i][j];
            pq.offer(new int[]{value,i,j});
            max = Math.max(max,value);
        }
        System.out.println(result);
    }
}