[BOJ 그리디] 과제 13904.JAVA

문제 링크 : https://www.acmicpc.net/problem/13904
문제 등급 : 제공하지 않음

13904번: 과제

문제 해결 프로세스

1. 마감일과 점수 중 점수를 기준으로 내림차순으로 정렬한다.
2. Set을 이용하여 해결할 수 있는 과제를 해결하고 점수를 획득한다.
   1. Set으로 마감일을 마감일의 최댓값 + 1을 포함하여 하나씩 입력한다.
   2. Set의 lower함수를 이용하여 가장 높은 점수의 과제 마감일부터 내림차순으로 찾는다.
   3. lower함수를 이용하면 현재 과제의 마감일보다 작은 마감일을 리턴 받는다.
   4. 현재 과제 마감일보다 작은 마감일에 과제를 해결하고 점수를 획득한다.
3. 획득한 최고 점수를 출력한다.

주요 로직

1. Set의 lower함수는 lower bound를 이용한 찾고자 하는 값보다 작은 값을 리턴하는 함수이다.
   1. Set에 1, 2, 3, 4, 5, 6이 있을 때 set.lower(5)를 하면 4를 리턴해준다.
2. 찾은 마감일(4)을 remove함수로 삭제하고 현재 과제의 점수를 더한다.

아래와 같이 소스를 공유합니다.

public class 과제 {
    public static class Node {
        int d, p;
        Node(int d, int p) {
            this.d = d;
            this.p = p;
        }
    }
    public static int point = 0;
    public static List<Node> list = new ArrayList<>();
    public static TreeSet<Integer> set = new TreeSet<>();
    public static Comparator<Node> compare = new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            return Integer.compare(o2.p, o1.p);
        }
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));

        int n = Integer.parseInt(br.readLine());
        int max = Integer.MIN_VALUE;

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int d = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            list.add(new Node(d, p));
            max = Math.max(max, d);
        }

        list.sort(compare);

        for(int i = 0; i <= max; i++)  set.add(i+1);
        for(int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            // int type으로 lower를 받았을 경우 NullPointException이 발생하여 
            // Class로 받아 null인지 체크
            Integer idx = set.lower(node.d+1);
            if(idx != null) {
                set.remove(idx);
                point += node.p;
            }
        }

        System.out.println(point);
    }
}