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

 

출력

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

 

풀이

투포인터 문제라서 포인터를 옮겨가면서 풀어야 된다고 생각했다.

그래서 생각한 방법은 N개의 반의 능력치를 오름차순 정렬하고, N개의 반 중 최솟값의 인덱스를 오른쪽(큰쪽)으로 옮기는 것이었다.

 

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

 

문제의 입력이 위와 같을 때, 먼저 각 반의 능력치를 정렬한다. 답(최댓값과 최솟값의 차)은 Integer.MAX_VALUE로 초기화 해준다.

 

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

 

각 반의 크기만큼 인덱스를 담을 배열을 만들고, 0으로 초기화 한다. 현재 인덱스는 각각 [0, 0, 0]이다. 

 

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

 

처음 각 인덱스가 가리키는 값은 위와 같다.

최댓값 : 14 , 최솟값 : 7, 차이 : 7 

현재 답은 Integer.MAX_VALUE로, 7보다 크기 때문에 값을 7로 갱신해준다.

최솟값은 7이기 때문에, 두 번째 반의 인덱스의 크기를 1 늘려준다. 현재 인덱스는 각각 [0, 1, 0] 이다.

 

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

 

최댓값 : 17 , 최솟값 : 12, 차이 : 5 

현재 답은 7로, 5보다 크기 때문에 값을 5로 갱신해준다.

최솟값은 12이기 때문에, 첫 번째 반의 인덱스의 크기를 1 늘려준다. 현재 인덱스는 각각 [1, 1, 0] 이다.

 

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

 

최댓값 : 17 , 최솟값 : 14, 차이 : 3 

현재 답은 5로, 3보다 크기 때문에 값을 3으로 갱신해준다.

최솟값은 14이기 때문에, 세 번째 반의 인덱스의 크기를 1 늘려준다. 현재 인덱스는 각각 [1, 1, 1] 이다.

 

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

 

최댓값 : 17 , 최솟값 : 15, 차이 : 2 

현재 답은 3으로, 2보다 크기 때문에 값을 2로 갱신해준다.

최솟값은 15이기 때문에, 세 번째 반의 인덱스의 크기를 1 늘려준다. 현재 인덱스는 각각 [1, 1, 2] 이다.

 

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

 

최댓값 : 54 , 최솟값 : 16, 차이 : 38 

현재 답은 2로, 38보다 작기 때문에 값을 갱신하지 않는다.

최솟값은 16이기 때문에, 첫 번째 반의 인덱스의 크기를 1 늘려준다. 현재 인덱스는 각각 [2, 1, 2] 이다.

 

위처럼 계속 반복을 해준다. 인덱스의 크기를 1 늘렸을 때, 그 인덱스가 학생 배열의 크기보다 크거나 같다면 (예제의 경우 4라면)  반복문에서 빠져나온다.

 

위의 과정을 정리해서 작성하면 아래와 같다.

 

1. 각 반의 능력치 정렬
2. 반의 수만큼 인덱스 배열을 만들고, 0으로 초기화
3. 각 반의 인덱스 위치의 능력치 중 최솟값과 최댓값을 구함
4. 최솟값과 최댓값의 차를 구하고 답 갱신
5. 최솟값의 인덱스를 1 늘림
6. 3, 4, 5를 반복
7. 5 이후 인덱스가 학생 수 보다 크다면 반복을 멈춘다.
8. 정답 출력

 

코드

 

package baekjoon;

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

public class BOJ2461 {

    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());
        int[][] students = new int[N][M];
        for (int i = 0; i <N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                students[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[] indexs = new int[N];
        for (int i = 0; i < N; i++) {
            Arrays.sort(students[i]);
            indexs[i] = 0;
        }
        int min = Integer.MAX_VALUE;
        while(true) {
            int partialMin = students[0][indexs[0]];
            int partialMax = students[0][indexs[0]];
            int minIdx = 0;
            for (int i = 1; i < N; i++) {
                if (partialMin > students[i][indexs[i]]){
                    partialMin = students[i][indexs[i]];
                    minIdx = i;
                }
                if (partialMax < students[i][indexs[i]]){
                    partialMax = students[i][indexs[i]];
                }
            }
            if ((partialMax - partialMin) < min) {
                min = (partialMax - partialMin);
            }
            if (++indexs[minIdx] >= M)
                break;
        }
        System.out.println(min);
    }
}

 

결과

 

문제	결과	메모리	시간	언어	코드 길이
2461	맞았습니다!!	135968 KB	3984 ms	Java 8	1687 B