[백준] 자바 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이하이다.

출력

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

---

테스트 케이스

 

입력 1

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

출력 1

70

 

입력 2

3 4
12 16 67 43
7 17 68 48
14 15 77 54

출력 2

2

 

---

접근

설명

각 값을 비교하여 최솟값을 찾아낼 때, 최댓값 - 최솟값도 저장하면서 결과를 도출합니다.

---

코드

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


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 map[][] = new int[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0; i<N; i++) {
			Arrays.sort(map[i]);
		}
		//포인터가 가르키는 인덱스 나타냄
		int arr[] = new int[N];
		int result = (int)10e9;
		int minArray = 0;
		while(true) {
			int max = 0;
			int min = (int)10e9;
			for(int i=0; i<N; i++) {
				//최대값 찾기
				if(map[i][arr[i]] > max) {
					max = map[i][arr[i]];
				}
				//최소값 찾기
				if(map[i][arr[i]] < min) {
					min = map[i][arr[i]];
					minArray = i;
				}
			}
			//제일 작은 값 선택.
			result = Math.min(result, max-min);
			arr[minArray]++;
			if(arr[minArray] == M) break;
		}
		System.out.println(result);
		br.close();
	}
}

---

주의

x