[2461]대표 선수

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

public class Main {
	static int N, M, answer;
	static Group[] gArr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		gArr = new Group[N*M];
		answer = 1000000000;
		
		int s = 0;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				gArr[s++] = new Group(i,Integer.parseInt(st.nextToken()));
			}
		}
		
		Arrays.sort(gArr);
		
		fn();
		System.out.println(answer);
	}

	static void fn() {
		//왼쪽 오른쪽 시작 지점, 구간 안에 포함된 반의 개수를 담을 변수
		int rv=0, lv=0, cnt=0;
		
		//왼쪽 포인터의 최대 거리
		int max = M*N-N;
		
		//오른쪽 포인터의 최대 거리
		int end = M*N;
		
		//구간에 반별 몇명이 포함되어 있는지 확인할 변수
		int check[] = new int[N];
		
		//왼쪽 포인터가 최고 거리 도달 할때 까지 반복
		while(lv<max) {
			
			//구간에 포함된 반의 수가 N보다 작을 경우 반복
			while(cnt<N) {
				
				//오른쪽 포인터가 끝에 도달하면 함수 종료
				if(rv==end) return;
				
				int num = gArr[rv++].num;
				//구간에 자신과 같은 반인 사람이 없는 경우
				if(check[num] == 0) {
					//지금까지 포함된 반의 갯수++
					cnt++;
				}
				
				//구간에 포함된 같은 반의 명수를 나타내는 check++
				check[num]++;
			}
			
			//왼쪽 포인터에서 한칸 전진했을 때  그 사람이 같은 반이라면
			while(lv<max && gArr[lv].num == gArr[lv+1].num) {
				//구간에 포함된 자신과 동일한 반의 명수 --;
				check[gArr[lv++].num]--;
			}
			
			answer = Math.min(answer, gArr[rv-1].score-gArr[lv].score);
			
			//만약 자신이 빠졌을때 같은 반을 가진 사람이 0명이라면
			if(--check[gArr[lv++].num]==0) {
				cnt--;
			}
		}
		
		
	}
	
	//반과 점수를 가지는 객체
	static class Group implements Comparable<Group>{
		int num;
		int score;
		public Group(int num, int score) {
			super();
			this.num = num;
			this.score = score;
		}
		
		public int compareTo(Group g) {
			return score-g.score;
		}
		
	}

}

다른사람풀이

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

public class Main {
    private static PriorityQueue<Student> pq = new PriorityQueue<>();

    private static class Student implements Comparable<Student>{
        int index;
        int value;

        public Student(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Student s) {
            return this.value - s.value;
        }
    }

    public static void main(String[] args) throws Exception{
        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[][] students = new int[2_000][2_000];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(students[i], Integer.MAX_VALUE);

            for(int j = 0; j < M; j++) {
                students[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(player(N, M, students));
    }

    private static int player(int n, int m, int[][] arr) {
        int[] pos = new int[n];
        int result = Integer.MAX_VALUE;
        int max = class1Classify(n, arr);

        int loop = n * m;

        while(loop-- > 0) {
        	//가장 작은 점수를 가지는 학생 리턴
            Student current = pq.poll();
            
            //둘중 가장 작은 차이를 result에 저장
            result = Math.min(result, max - current.value);

			//현재 학생의 반에서 빠진 학생의 수 ++
            pos[current.index]++;
            //현재 학생의 반에서 빠진 학생의 수가 N과 같을 경우 탈출
            if(pos[current.index] == n) break;

			//현재 빠진 학생의 반에서 빠진 학생 다음으로 점수가 높은 학생을
            //대려와 원래 있던 max와 점수를 비교하여 큰 걸 max에 넣음
            max = Math.max(max, arr[current.index][pos[current.index]]);
            //대려왔으니 pq에 넣는다.
            pq.offer(new Student(current.index, arr[current.index][pos[current.index]]));
        }

        return result;
    }

	//반 별 오름차순 정렬 후 각 반의 제일 작은값 중에서 제일 큰 값을 가진 반의 값을 max로 반환
    private static int class1Classify(int n, int[][] arr) {
        int max = 0;
	
 
        for(int i = 0; i < n; i++) {
            Arrays.sort(arr[i]);

            max = Math.max(max, arr[i][0]);
            pq.offer(new Student(i, arr[i][0]));
        }

        return max;
    }
}