[백준] 2461번 : 대표 선수 - 자바(JAVA)

https://www.acmicpc.net/problem/2461

2461번: 대표 선수

 

문제 해석

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~1000의 범위를 가지기 때문에 완전탐색할경우 시간 복잡도를 초과할 것 같습니다.

정렬을 하고 이분 탐색을 하면 어떨까?라는 생각이 들지만 결국 n개의 학급을 모두 고려해야 합니다.

DP를 활용하면 어떨까? 라는 생각이 들지만 중복되는 부분이나 이 문제의 작은 해로 큰 문제를 해결하는 부분이 보이지 않습니다.

탐욕 법을 이용할 수도 없어 보이고 그래프를 만들 수도 없어 보입니다.

 

도저히 감이 오지 않아 "투 포인터"라는 방법을 사용해야 한다는 것을 알게 되었고 풀이 방법은 다음과 같았습니다.

 

1. 능력치 순서대로 학생을 정렬한다. 이때 학급의 정보를 확인할 수 있어야 합니다.

2. 투 포인터를 활용해 모든 학급의 학생이 포함되는 연속된 범위를 찾아냅니다.

3. 해당 범위에서 최댓값-최솟값이 최소가 되는 값으로 갱신합니다.

 

코드

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

public class Main_2461_대표선수 {

    static class Student implements Comparable<Student> {
        int ability;
        int classNum;

        public Student(int ability, int classNum) {
            this.ability = ability;
            this.classNum = classNum;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "ability=" + ability +
                    ", classNum=" + classNum +
                    '}';
        }

        @Override
        public int compareTo(Student o) {
            return this.ability - o.ability;
        }
    }

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

        Student[] students = new Student[N * M];

        int index = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                students[index++] = new Student(Integer.parseInt(st.nextToken()), i);
            }
        }
        //능력치 순서로 정렬
        Arrays.sort(students);

        //투포인터 선언
        int leftPoint = 0, rightPoint = 0;
        int result = Integer.MAX_VALUE;
        //학급을 세기위한 변수 선언
        int[] count = new int[N];

        while (leftPoint < N * M - 1 && rightPoint < N * M - 1) {
            //오른쪽 포인터 이동
            while (rightPoint < N * M - 1) {
                //학급 counting
                count[students[rightPoint++].classNum]++;
                if (haveAllClass(count)) {
                    break;
                }
            }
            //왼쪽 포인터 당기기
            //1보다 크다는것은 왼쪽포인터를 당기더라도 오른쪽에 해당 학급이 존재하므로 포인터를 당기는것에 이상이 전혀 없음.
            while (count[students[leftPoint].classNum] > 1) {
                count[students[leftPoint++].classNum]--;
            }

            //모든 학급을 포함하는 최소범위를 탐색했으니 값 갱신
            if (haveAllClass(count)) {
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;

                for (int i = leftPoint; i < rightPoint; i++) {
                    min = Math.min(min, students[i].ability);
                    max = Math.max(max, students[i].ability);
                }
                result = Math.min(result, max - min);
            }

            //왼쪽 포인터 오른쪽으로 한칸 이동
            count[students[leftPoint++].classNum]--;
        }

        System.out.println(result);


    }

    private static boolean haveAllClass(int[] count) {
        for (int cnt : count) {
            if (cnt == 0) {
                return false;
            }
        }
        return true;
    }
}