백준 2109번 - 순회강연

문제

백준 2109번 - 순회강연

아이디어

• 돈을 가장 많이 벌기 위해서는 하루에 한 곳만 강연이 가능하므로 동일한 날에는 강연료가 더 많은 강연을 하는 것이 유리하다.
• N개의 강연을 일수 오름차순, 일수가 같으면 강연료 내림차순으로 정렬한다.
• 우선순위큐를 준비한다. 우선순위큐의 사이즈가 진행한 강연의 개수가 된다.
• 정렬된 강연들 순서대로 강연료를 우선순위큐에 저장한다. 그러다가 현재 강연의 일수보다 진행된 강연의 수가 더 많다면 강연 하나를 포기해야 하므로 qu.poll()로 강연료가 제일 적은 강연을 제외시킨다.
• 이렇게 d일 이내에 진행한 강연에서 최대 강연료만 얻을 수 있도록 하고, 우선순위큐에 남아있는 수의 합이 정답이다.

예상 시간 복잡도

• 강연의 수 : N
• 예상 시간 복잡도 : O(N log N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_2109 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            arr[i][0] = d;
            arr[i][1] = p;
        }

        //일수 오름차순, 일수가 같으면 강연료 내림차순 정렬
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o2[1] - o1[1];
            }
            return o1[0] - o2[0];
        });

        //큐의 사이즈 = 진행한 강연의 개수
        PriorityQueue<Integer> qu = new PriorityQueue<>();

        for (int[] lecture : arr) {

            int d = lecture[0];
            int p = lecture[1];

            qu.offer(p);

            //강연은 하루에 한 개만 할 수 있다.
            //강연의 개수가 일수를 넘어가면 가장 적은 강연료의 강연을 제거한다.
            if (qu.size() > d) {
                qu.poll();
            }
        }

        int sum = 0;

        while (!qu.isEmpty()) {
            sum += qu.poll();
        }

        System.out.println(sum);
    }
}