[BOJ] 백준 2461 : 대표 선수 (java)

• 🧪 2461 대표 선수

• 📝 문제

• 🧐 핵심 로직 

• 💻 최종 코드 (2680 ms)

🧪 2461 대표 선수

---

난이도 : 🌟 골드 2
유형 : 투포인터

https://www.acmicpc.net/problem/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. 학생들의 성적 데이터를 이용해 주어진 조건을 만족하는 최소 점수 차이를 계산한다.

 

2. 프로그램은 입력 데이터를 처리하여 학생들의 성적을 저장하고, 이를 기반으로 최소 점수 차이를 찾는 알고리즘을 실행한다.

    2 - 1) 첫 번째 줄에서 n(학생의 수)과 m(각 학생의 점수 개수)을 읽어온다.

    2 - 2) 이후 학생들의 성적 데이터를 2차원 배열 students에 저장한다.

 

3. 각 학생의 점수를 오름차순으로 정렬한 뒤, 모든 학생의 현재 최소 점수를 추적하기 위해 indexes 배열을 초기화한다.

 

4. 최소 점수 차이를 계산하기 위해 아래의 단계를 반복한다.

    4 - 1) 현재 각 학생의 최소 점수 중 가장 작은 값(minScore)과 가장 큰 값(maxScore)을 찾는다.

    4 - 2) maxScore - minScore가 현재 저장된 최소 점수 차이(res)보다 작으면 res를 갱신한다.

    4 - 3) minScore를 제공하는 학생의 점수를 다음 점수로 갱신하기 위해 해당 학생의 indexes 값을 증가시킨다.

    4 - 4) 만약 특정 학생의 점수가 모두 처리되었다면 반복을 종료한다.

 

5. 계산된 최소 점수 차이를 출력한다.

 

💻 최종 코드 (2680 ms)

---

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

public class Main {

    static BufferedReader br;
    static int n, m, res;
    static int[] indexes;
    static int[][] students;
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        res = Integer.MAX_VALUE;

        fillBoard();
        makeIndexArray();
        selectPlayer();

        System.out.println(res);

        br.close();
    }

    private static void fillBoard() throws Exception {

        students = new int[n][m];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                students[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    private static void makeIndexArray() {

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

    private static void selectPlayer() {

        while (true) {

            int minScore = students[0][indexes[0]];
            int maxScore = students[0][indexes[0]];
            int minIdx = 0;

            for (int i = 1; i < n; i++) {
                if (minScore > students[i][indexes[i]]) {
                    minScore = students[i][indexes[i]];
                    minIdx = i;
                }

                if (maxScore < students[i][indexes[i]]) {
                    maxScore = students[i][indexes[i]];
                }
            }

            if (maxScore - minScore < res) {
                res = maxScore - minScore;
            }

            if (++indexes[minIdx] >= m) break;
        }
    }
}
`