[Java | 투포인터 | 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이상 10^9이하이다.

 

출력

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

 

예제 입력1

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

 

예제 출력1

2

 

예제 입력2

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

 

예제 출력2

70

 

☄️ 정답코드

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

public class Main {
    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());

        List<Student> students = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                long stat = Long.parseLong(st.nextToken());
                students.add(new Student(stat, i));
            }
        }

        Collections.sort(students);

        long ans = Long.MAX_VALUE;

        int s = 0;
        int[] classes = new int[N];
        for (int e=0; e<students.size();e++) {
            Student student = students.get(e);
            classes[student.idx]++;

            boolean flag = true;
            for (int i = 0; i < N; i++) {
                if(classes[i] == 0) {
                    flag = false;
                    break;
                }
            }
            if(!flag) continue;

            while(true) {
                Student minStu = students.get(s);
                ans = Math.min(ans, student.stat - minStu.stat);
                s++;
                classes[minStu.idx]--;
                if(classes[minStu.idx] == 0) break;
            }
        }

        System.out.println(ans);
    }

    static class Student implements Comparable<Student> {
        long stat;
        int idx;

        public Student(long stat, int idx) {
            this.stat = stat;
            this.idx = idx;
        }

        public int compareTo(Student s) {
            return Long.compare(this.stat, s.stat);
        }
    }
}

 

🪐 풀이

투포인터

 

N(학급의 수)과 M(각 학급의 학생 수)가 각각 최대 1000이기 때문에

모든 경우를 탐색하면 1000의 3승, O(10^9) => 절대 안되겠죠?!

 

O(N^2)으로 할 수 있는 방법을 생각해보던 중 모든 학생들을 점수 오름차순으로 일렬로 늘어놓고,

쭉 훑어보면 되겠다는 생각을 했다

 

생각보다 코드 구현은 쉬웠기 때문에 코드는 찬찬히 보시길!