[자바] 백준 19700 - 수업 (java)

목차

문제 : boj19700

 

 

필요 알고리즘

• 그리디, 이분탐색
  
  • 그리디 아이디어만 있으면 난이도가 확 줄어드는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  하나의 아이디어를 넣으면 난이도가 급하락하는 좋은 문제이다. 입력받은 h와 k를 h 기준으로 내림차순으로 정렬한다고 해보자. 그리고 h가 높은 순서대로 확인을 할껀데, 이래도 되는 이유가 '학생들의 키는 모두 다르다' 라는 조건이 있기 때문이다.

 

  이렇게되면 난이도가 하락하는 이후는, h를 기준으로 큰 순서대로 본다면 이후 h는 무시하고 k만 보면 되기 때문이다. 키가 큰 순서대로 보면서 아래의 로직을 계속 그리디로 진행하면 된다.

1. k명 미만으로 구성된 그룹을 찾는다..

2. 해당 그룹의 그룹원을 1명 늘린다.

 

  내 경우 '1'은 이분탐색을 사용해 찾았다. 그리고 '2'를 편하게 하기 위해 group 배열을 두었다.

group[x] 는 x명인 그룹의 갯수이다. 3명인 그룹이 4개 있다면 group[3] = 4이고, 이후 k가 4인 녀석이 있다면 group[3]은 3이 되고, group[4]++ 이 된다.

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            list.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }
        Collections.sort(list, (o1, o2) -> o2[0]-o1[0]);

        TreeSet<Integer> exist = new TreeSet<>();
        int[] group = new int[n+1];
        group[0] = n;
        for (int[] cur : list) {
            Integer find = exist.lower(cur[1]);
            find = find==null?0:find;
            if (--group[find] == 0) {
                exist.remove(find);
            }
            ++group[find+1];
            exist.add(find+1);
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) answer += group[i];
        System.out.println(answer);
    }
}