문제 접근

우선, 문제를 읽어보면, 학생은 자신의 키보다 큰 사람이 Ki명 이하힌 그룹에만 들어갈 수 있다. 문제를 해석해보자.
즉, 자기 입장에서 나보다 큰 사람들이 이전에 모두 그룹에 배치되어있는 상황이라면, 나는 그냥 내가 들어갈 수 있는 그룹 중에서 가장 사람이 많이 차있지만 또 나보다 키큰 사람의 수(이미 배치된 사람들의 수)가 Ki가 되지 않는 그런 그룹 안에 들어가면 된다.

여기서, 내가 들어갈 수 있는 그룹 중에서 가장 인원이 많이 찬 그룹에 들어가야 하는 이유는, 뒤에 나올 사람중에서 나보다 키는 작지만 Ki가 더 작은값을 갖는 사람이 있을 수 있기 때문에 내가 들어갈 수 있는 최적의 자리에 들어가는것임.

즉, 키 순서로 정렬을 하고 순차적으로 탐색하며 그룹에 넣어주거나 새그룹을 만들거나 -> 이게 바로 그리디이고,
내가 그룹에 들어가야할때 최적의 그룹을 찾는 방법이 바로 이분탐색을 써야 하는 부분이다.

이번에 이 문제를 풀면서 처음 알게 된 내용은 TreeSet의 lower 함수가 있다는 점이다... 그동안 자바에서는 이분탐색에서 upper_bound나 lower_bound를 구할때 직접 구현해야하는 줄 알았다. 하지만 TreeSet의 기본적으로 정렬된다는 특징을 사용해서 lower라는 메소드를 제공해주고 있었다. 이는 레드-블랙 트리의 특징 답게 O(logN)의 시간이다.

• E lower(E target) 메소드는 인자로 준 타깃값보다 작지만 그 중 가장 큰 원소를 리턴한다. 만약 없다면 null을 반환한다.

하지만, 이 문제는 동일한 크기를 가진 그룹이 여러개 있을 수 있기 때문에 해당원소크기를 가진 그룹의 갯수 정보도 같이 저장해줘야 한다. 이를 위해 int[] group = new int[N+1]을 선언했다.

문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Student> students = new ArrayList<>();
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            Student s = new Student(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            students.add(s);
        }
        Collections.sort(students, (s1, s2) -> {
            return s2.h - s1.h;
        });

        int result = 1;
        TreeSet<Integer> set = new TreeSet<>();
        int[] countOfGroup = new int[N + 1];
        set.add(1);
        countOfGroup[1]++; // 1명인 그룹이 지금 한개 있다.

        for (int i = 1; i < N; i++) {
            Student s = students.get(i);
            Integer findGroupCurSize = set.lower(s.k);
            if (findGroupCurSize == null) { // 새그룹을 추가해야함.
                set.add(1);
                countOfGroup[1]++;
                result++;
            } else {
                countOfGroup[findGroupCurSize]--;
                if (countOfGroup[findGroupCurSize] == 0) set.remove(findGroupCurSize);

                countOfGroup[findGroupCurSize + 1]++;
                if (countOfGroup[findGroupCurSize + 1] == 1) set.add(findGroupCurSize + 1);
            }
        }

        System.out.println(result);
    }

    static class Student {
        final int h;
        final int k;

        public Student(int h, int k) {
            this.h = h;
            this.k = k;
        }
    }

}

처음에는 이 문제를 PQ 두개를 써서 정렬순서를 다르게 한 다음, 두개를 양방향으로 처리하면서 그룹을 만들어주려고 했다. 하지만 그리디라는 설명을 스터디에서 듣고 감을 잡을 수 있었다... 인생 첫 골드1 문제였는데 그래도 엄청 어려운 문제는 아니였던 것 같고, 문제가 깔끔해서 좋았다. 또 우리학교 이름도 나와서 좀 반가운 문제였다.