방과후
ALGORITHM NOTE약 1분

BOJ 2461 - 대표 선수

제 능력치는 53만입니다

#algorithm#boj#gold#priority-queue#sorting
아카이브로 돌아가기

문제 링크

문제

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이상 10^9이하이다.

출력

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

풀이

각 반에서 정확히 한 명씩 뽑아야 하므로, 현재 각 반에서 선택된 학생들의 최댓값과 최솟값 차이를 계속 관리하면 된다.

코드에서는 각 반 점수를 내림차순 정렬하고, 각 반의 첫 원소를 우선순위 큐에 넣는다. 큐에서는 현재 가장 큰 값을 꺼내고, 그 반의 다음 학생을 넣는 방식으로 후보 구간을 움직인다. 동시에 현재 선택된 값들 중 최솟값 minNum을 유지하면서 max - min의 최소를 갱신한다.

어떤 반에서 더 이상 다음 학생이 없으면 더 이상 모든 반에서 하나씩 뽑는 구성이 불가능하므로 종료한다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static class Student implements Comparable<Student> {
        int room, idx, weight;
        Student(int room, int idx, int weight) {
            this.room = room;
            this.idx = idx;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Student o) {
            return o.weight - this.weight;
        }
    }
 
    static int N, M, minNum = Integer.MAX_VALUE;
    static Integer[][] arr;
    static PriorityQueue<Student> pq = new PriorityQueue<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new Integer[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr[i], Collections.reverseOrder());
        }
 
        for (int i = 0; i < N; i++) {
            pq.add(new Student(i, 0, arr[i][0]));
            minNum = Math.min(minNum, arr[i][0]);
        }
 
        System.out.println(solve());
    }
 
    static int solve() {
        int ans = Integer.MAX_VALUE;
        while (!pq.isEmpty()) {
            Student cur = pq.poll();
            ans = Math.min(ans, cur.weight - minNum);
 
            if (cur.idx == M - 1) break;
            int next = arr[cur.room][cur.idx + 1];
            minNum = Math.min(minNum, next);
            pq.add(new Student(cur.room, cur.idx + 1, next));
        }
 
        return ans;
    }
}

복잡도

  • 시간 복잡도: O(NMlog⁡N)O(NM \log N)
  • 공간 복잡도: O(NM)O(NM)

마무리

각 반에서 한 명씩 뽑는 문제는 현재 구간의 최대값과 최소값을 관리하는 형태로 자주 바뀐다. 우선순위 큐로 한 반씩 포인터를 움직이는 아이디어가 핵심이다.