백준 2461번: 대표선수 (JAVA)

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

2461번: 대표 선수

문제

KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.

이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, N=3, M=4인 경우 학생들의 능력치가 1반=[12, 16, 67, 43],  2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로 주어질 때, 각 학급으로부터 능력치 16, 17, 15를 가진 학생을 각각 선택하면, 최댓값과 최솟값의 차이가 17-15=2로 최소가 된다. 

대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학급 학생들의 능력치를 나타내는 M개의 양의 정수가 하나의 빈칸을 사이에 두고 주어진다. 능력치는 0이상 109이하이다.

출력

대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 하나의 정수로 출력한다.

 

---

 

풀이

이차원 int 배열 school을 만들어, i반의 학생을 school[i]에 저장한다. 포인터를 사용하기 위해, 각각의 school[i]를 정렬해준다.

각각의 반의 index에 대응하는 N개의 포인터를 0부터 시작하여, 각 반의 가장 능력치가 작은 학생 N명을 대표로 뽑는다. 최대 최소 차이를 구하여 현재 기록한 차이의 최솟값보다 작으면 갱신해준다. N명의 대표 중 능력치가 가장 작은 학생을 뽑아, 해당 학생의 반의 포인터를 1 증가시켜 해당 학생을 대표에서 제외하고, 반의 다음 학생을 대표에 넣는데. 이 과정을 어느 한 포인터가 index 밖으로 나가기 전까지 반복하면 된다.

'투 포인터' 문제집을 풀다보니 풀이 방법을 생각해 낼 수 있었던 듯하다. 나중에 쌩으로 다시 보면 기억할까? 나중에 복습하자.

 

코드

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

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());
        Student[][] school = new Student[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                school[i][j] = new Student(Integer.parseInt(st.nextToken()), i);
            }
        }

        for (int i = 0; i < N; i++) {
            Arrays.sort(school[i]);
        }
        int[] pt = new int[N];
        PriorityQueue<Student> pq = new PriorityQueue<>();
        int ans = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < N; i++) {
            if (school[i][0].num > max) max = school[i][0].num;
            pq.offer(school[i][0]);
        }

        while (true) {
            Student cur = pq.poll();
            int diff = max - cur.num;
            if (diff < ans) ans = diff;

            if (++pt[cur.classNo] == M) break;

            Student nxt = school[cur.classNo][pt[cur.classNo]];
            pq.offer(school[cur.classNo][pt[cur.classNo]]);
            if (nxt.num > max) max = nxt.num;
        }
        System.out.println(ans);
    }


    static class Student implements Comparable<Student>{
        int num;
        int classNo;

        public Student(int num, int classNo) {
            this.num = num;
            this.classNo = classNo;
        }

        public int compareTo(Student o) {
            return this.num - o.num;
        }
    }
}