[Java] 백준 2461번 - 대표 선수

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

2461번: 대표 선수

[문제 풀이]

처음엔 단순 조합을 통해 가능한 모든 조합을 계산하는 방식으로 풀이하였지만, 시간초과로 인해 다시 문제를 생각해보았습니다. 

 

각각의 반의 선수의 능력치를 우선 정렬합니다.

투포인터 방식처럼 각 반의 index 0 부터 시작하여, 3개의 반중 최소값을 가지는 반의 index를 오른쪽 1 이동시키며 차이값을 구합니다.

 

12      12     16     16     16      43     43      67      67      67
7   ->  17  -> 17 ->  17  -> 17  ->  17  -> 48  ->  48  ->  68  ->  68
14      14     14     15     54      54     54      54      54      77

 

마지막에 1반 : 67 , 2반 : 68 , 3반: 77 일때, 최소값을 가지는 1반의 값이 더이상 없으므로 계산이 종료됩니다.

이 과정을 반복하며 구해진 차이값의 최솟값을 출력합니다.

 

- 최소값을 계속 뽑아내야 하기 때문에 우선순위큐를 사용해 구현하였습니다.

- 우선순위 큐를 이용하여 각 반의 index 0을 넣어 초기화 한 후, poll 한 값의 반에서 다음 index값을 우선순위에 넣어주는 방식으로 구현하였습니다.

 

[정답 코드]

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

class Student implements Comparable<Student>{
    int index = 0;
    int amount = 0;
    public Student(int index, int amount) {
        this.index = index;
        this.amount = amount;
    }

    @Override
    public int compareTo(Student o) {
        return amount - o.amount;
    }
}

public class Main {
    public static int N;
    public static int M;
    public static PriorityQueue<Integer>[] student;
    public static PriorityQueue<Student> pq = new PriorityQueue<>();
    public static int min = Integer.MAX_VALUE;
    public static int max = 0;
    public static int answer = Integer.MAX_VALUE;
    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());
        student = new PriorityQueue[N];
        for(int i=0;i<N;i++) {
            student[i] = new PriorityQueue<>();
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                student[i].offer(Integer.parseInt(st.nextToken()));
            }
        }
        for(int i=0;i<N;i++) {
            int index = i;
            int amount = student[i].poll();
            pq.offer(new Student(index, amount));
            if(amount > max) {
                max = amount;
            }
            if(amount < min) {
                min = amount;
            }
        }
        answer = max - min;
        pick();
        System.out.println(answer);
    }
    public static void pick() {
        // 최소값 꺼냄
        Student s = pq.poll();
        // 다음 최소값으로 갱신
        min = pq.peek().amount;
        if(student[s.index].isEmpty()) {
            // 최소값의 index = N-1
            return;
        }
        // 최소값이었던 index의 다음 값 넣어줘야함
        int p = student[s.index].poll();
        pq.offer(new Student(s.index, p));
        if(p > max) {
            max = p;
        }
        if(p < min) {
            min = p;
        }
        if(answer > max - min) {
            answer = max - min;
        }
        pick();
    }
}

/*
12 16 43 67
7 17 48 68
14 15 54 77

67 68 77

10 20 30
40 50 60
70 80 90
100 110 120

30 40 70 100

최소값인걸 +1, 최소값의 index = N-1이면 끝

 */