[BaekJoon] 19700 수업 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
    static int studentCount;
    static Map<Integer, Integer> studentInfos;
    static TreeSet<Team> teams;

    static void input() {
        Reader scanner = new Reader();

        studentCount = scanner.nextInt();
        studentInfos = new TreeMap<>(Collections.reverseOrder());
        teams = new TreeSet<>();

        for (int idx = 0; idx < studentCount; idx++) {
            int height = scanner.nextInt();
            int maxLonger = scanner.nextInt();
            studentInfos.put(height, maxLonger);
        }
    }

    /*
     * 주어진 학생의 키와 최소 등수 정보를 학생의 키 기준 내림차순으로 정렬한다
     * 그럼 앞에서부터 뒤로 반복문을 돌리면 키가 큰 학생부터 작은 학생 순으로 반복문이 돌게 된다
     * 각 학생마다 팀에서 자신보다 키 큰 사람의 수에 제한이 있기 때문에 키가 큰 학생부터 팀을 구성한다
     *
     * 각 학생은 팀에 포함된 학생 수가 제한된 수, 즉 등수보다 작은 그룹 중 하나에 할당시켜줘야 한다
     * 이때, 팀의 개수를 최소로 만들어줘야하므로, 제한이 작은 학생,
     * 즉 등수를 나타내는 수가 작은 학생들을 기존 팀에 넣기 위해 할당될 수 있는 팀 중 가장 인원수가 많은 팀에 넣어주어야 한다
     *  - 그래야 등수를 나타내는 수가 작은 학생들도 기존 팀에 포함될 수 있는 확률이 높아진다
     *
     * 그러므로 할당될 수 있는 팀 중 가장 인원이 많은 팀에 해당 학생을 포함시킨다
     *
     * 이때, TreeSet의 lower()를 이용하여 팀이 포함하는 인원수가 특정 인원수 바로 이전에 해당하는 팀을 찾아낼 수 있다
     * 이를 이용하여 할당될 수 있는 팀 중 가장 인원이 많은 팀을 구하고 해당 팀에 현재 학생을 포함시킨다
     */
    static void solution() {
        for (int height : studentInfos.keySet()) {
            if (teams.isEmpty()) {
                teams.add(new Team(height, 1));
                continue;
            }

            Team nearestLowerTeam = teams.lower(new Team(height, studentInfos.get(height)));
            if (nearestLowerTeam == null) {
                teams.add(new Team(height, 1));
                continue;
            }

            nearestLowerTeam.teamMemberCount++;
        }

        System.out.println(teams.size());
    }

    static class Team implements Comparable<Team> {
        int maxHeight;
        int teamMemberCount;

        public Team(int maxHeight, int teamMemberCount) {
            this.maxHeight = maxHeight;
            this.teamMemberCount = teamMemberCount;
        }

        @Override
        public int compareTo(Team o) {
            if (teamMemberCount != o.teamMemberCount) {
                return teamMemberCount - o.teamMemberCount;
            }
            return maxHeight - o.maxHeight;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}