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

문제 유형
포인터, 우선순위 큐

풀이 방법 도출

1. 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.
이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다.
2. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 
3. 대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력하는 프로그램을 작성하시오.
4. 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다.

우선순위큐를 사용해서 풀 수 있는데, 얻을 수 있는 힌트는 다음과 같습니다.

"최대값과 최소값만 알면된다"

최대값과 최소값을 효율적으로 관리하는 자료구조는 우선순위 큐가 존재합니다.

이중 우선 순위 큐를 통해 최대힙, 최소힙을 만듭니다.

int[][] arr = new int[n][m];

PriorityQueue<Node> maxQ = new PriorityQueue <>((n1, n2) - > n2.value - n1.value);
PriorityQueue<Node> minQ = new PriorityQueue <>((n1, n2) - > n1.value - n2.value);

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());

    }
}


for (int i = 0; i < n; i++) {
    Arrays.sort(arr[i]);
}

for (int i = 0; i < n; i++) {
    Node node = new Node(arr[i][0], i, 0);

    maxQ.add(node);
    minQ.add(node);
}

이후 반을 오름차순으로 정렬한 후, 각 반의 1번 선수로 최소힙, 최대힙으로 구성합니다.

int ans = Integer.MAX_VALUE;


while (!maxQ.isEmpty() && !minQ.isEmpty()) {

    Node maxNode = maxQ.peek();
    Node minNode = minQ.poll();

    minNode.alive = false;

    ans = Math.min(maxNode.value - minNode.value, ans);


    minNode.valueIdx++;


    if (minNode.valueIdx >= m) break;

    int value = arr[minNode.arrayIdx][minNode.valueIdx];

    Node newNode = new Node(value, minNode.arrayIdx, minNode.valueIdx);

    minQ.add(newNode);
    maxQ.add(newNode);

    while (!maxQ.isEmpty() && !maxQ.peek().alive) maxQ.poll();
    while (!minQ.isEmpty() && !minQ.peek().alive) minQ.poll();

}

오름차순으로 정렬했기 때문에 최소값과 최대값의 차이를 줄이기 위해선 최소값을 가지는 반의 포인터를 1 증가시켜 해당 포인터가 가르키는 Node를 우선순위큐에 삽입합니다.

시간 복잡도
O(n * m log n * m)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Node {
	
	int value;
	int arrayIdx;
	int valueIdx;
	boolean alive;
	
	Node (int value, int arrayIdx, int valueIdx) {
		this.value = value;
		this.arrayIdx = arrayIdx;
		this.valueIdx = valueIdx;
		this.alive = true;
	}
	
}


public class Main {
	
	
	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[][] arr = new int[n][m];
		
		PriorityQueue<Node> maxQ = new PriorityQueue<>((n1,n2) -> n2.value - n1.value);
		PriorityQueue<Node> minQ = new PriorityQueue<>((n1,n2) -> n1.value - n2.value);
		
		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());
				
			}
		}
		
		
		for (int i=0; i<n; i++) {
			Arrays.sort(arr[i]);
		}
		
		for (int i=0; i<n; i++) {
			Node node = new Node(arr[i][0], i, 0);
			
			maxQ.add(node);
			minQ.add(node);
		}
		
		int ans = Integer.MAX_VALUE;
		
		
		while (!maxQ.isEmpty() && !minQ.isEmpty()) {
			
			Node maxNode = maxQ.peek();
			Node minNode = minQ.poll();
			
			minNode.alive = false;
			
			ans = Math.min(maxNode.value - minNode.value, ans);
			
			
			minNode.valueIdx++;
			
			
			if (minNode.valueIdx >= m) break;
			
			int value = arr[minNode.arrayIdx][minNode.valueIdx];
			
			Node newNode = new Node(value, minNode.arrayIdx, minNode.valueIdx);
			
			minQ.add(newNode);
			maxQ.add(newNode);
			
			while (!maxQ.isEmpty() && !maxQ.peek().alive) maxQ.poll();
			while (!minQ.isEmpty() && !minQ.peek().alive) minQ.poll();
		
		}
		
		System.out.println(ans);
		
		
	}

	
}