[백준] 대표 선수 (JAVA)

대표선수_2461

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

2461번: 대표 선수

문제 설명

학급의 수 N과 각 학급의 학생수 M이 주어지고

각 학생들은 능력치를 가지고있다.

학급마다 한 명씩 대표를 뽑아 경기를 치른다.

대표선수들의 능력치 중 최댓값과 최솟값의 차이를 구했을 때 최소의 차이를 만드는 대표선수를 뽑아야한다.

이때 차잇값을 구하는 문제이다.

---

문제 풀이

생각 과정

내가 생각한 방식은 학생들을 학급에 관계없이 모두 리스트에 넣고

능력치에 따라서 정렬을 해준다.

다음 투포인터를 활용하여 각 포인터사이에 모든 학급이 포함되도록 포인터위치를 설정한다.

해당 범위 내의 최솟값과 최댓값을 구해서 차이를 갱신해준다.

갱신 후 왼쪽 포인터를 한 칸 옮겨준다.

만약 모든 범위 내에 모든 학급이 포함되지 않았다면 오른쪽 포인터를 한 칸 옮겨준다.

구현

public class 대표선수_2461 {
    static int N, M;
    static int count[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());   // 학급 수
        M = Integer.parseInt(st.nextToken());   // 학생 수
        count = new int[N]; // 각 학급의 학생이 몇 명 사용됐는가
        List<Student> students = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                students.add(new Student(i, Integer.parseInt(st.nextToken())));
            }
        }
        Collections.sort(students); // 능력치로 정렬

        int left = 0;
        int right = 0;
        int answer = Integer.MAX_VALUE;

        while (left < N * M - 1 && right < N * M - 1) {
            while (right < N * M - 1) { //모든 학급이 포함되도록 right 변경
                count[students.get(right++).num]++;
                if (check()) break;
            }
            while (count[students.get(left).num] > 1) { //모든 학급이 포함되도록 left 변경
                count[students.get(left++).num]--;
            }
            if (check()) {  //모든 학급 포함시 값 갱신
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;

                for (int i = left; i < right; i++) {
                    min = Math.min(min, students.get(i).stat);
                    max = Math.max(max, students.get(i).stat);
                }
                answer = Math.min(answer, max - min);
            }
            count[students.get(left++).num]--;  // left 변경
        }
        System.out.println(answer);
    }

    public static boolean check() { //모든 학급이 포함되었는지 확인하는 함수
        for (int cnt : count) {
            if (cnt == 0) return false;
        }
        return true;
    }

    static class Student implements Comparable<Student> {
        int num;
        int stat;

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

        @Override
        public int compareTo(Student s) {
            return this.stat - s.stat;
        }
    }
}

 

주의점