최대 수입 스케쥴(PriorityQueue 응용문제)

현수는 유명한 강연자이다. N개의 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다. 각 기업이 요청한 D와 M을 바탕으로 가장 많은 돈을 벌 수 있도록 강연 스케줄을 짜야한다. 단, 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

 

입력 설명

• 첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어진다.
• 다음 N개의 줄에 각 기업이 제시한 강연료 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례대로 주어진다.
  (M은 강연료, D는 해당 강연을 해야 하는 마감 기한이다)

출력 설명

• 첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

입력 예제 

6
50 2
20 1
40 2
60 3
30 3
30 1

 

출력 예제 

150

 

문제 풀이 과정

1. 우선순위 큐 사용: 각 날짜마다 가능한 강연들 중 가장 많은 강연료를 얻기 위해 우선순위 큐(PriorityQueue)를 사용한다. 큐는 강연료를 내림차순으로 정렬하여, 매일 가능한 최대 금액의 강연을 선택할 수 있다.
2. 정렬: 강연을 날짜 기준으로 내림차순 정렬하여 나중 날짜부터 확인한다.
3. 그리디 알고리즘: 매일 가능한 강연 중 가장 높은 보수를 얻는 방식으로 스케줄링을 최적화한다.

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 강연 정보 저장을 위한 lecture 클래스
class lecture {
    int money, date; // money: 강연료, date: 강연 가능한 마지막 날짜

    // 생성자: 강연료와 강연 가능 날짜 초기화
    public lecture(int money, int date) {
        this.money = money;
        this.date = date;
    }
}

class Main {
    static int n; // 강연 요청 개수
    static int max = Integer.MIN_VALUE; // 가장 큰 날짜 저장 (강연 가능 최대 날짜)

    // 최대 수입을 계산하는 함수
    public static int solution(ArrayList<lecture> arr) {
        int answer = 0; // 최종 수입
        // 우선순위 큐: 큰 금액이 먼저 오도록 설정 (내림차순)
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Comparator.reverseOrder());

        // 날짜를 기준으로 내림차순 정렬 (가장 늦은 날짜부터 처리하기 위해)
        arr.sort((a, b) -> b.date - a.date);

        int j = 0; // 현재 강연의 인덱스를 가리킬 변수
        // max부터 1까지 역순으로 날짜를 처리
        for (int i = max; i >= 1; i--) {
            // 현재 날짜(i)보다 크거나 같은 날짜의 강연을 모두 우선순위 큐에 넣는다
            while (j < n && arr.get(j).date >= i) {
                pQ.offer(arr.get(j).money); // 강연료를 큐에 넣음
                j++;
            }

            // 큐에 강연료가 있으면 가장 큰 금액의 강연을 선택 (poll)
            if (!pQ.isEmpty()) {
                answer += pQ.poll(); // 하루에 하나의 강연만 할 수 있으므로 가장 높은 보수 선택
            }
        }
        return answer; // 최종 수입 반환
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // 강연 요청 개수 입력
        ArrayList<lecture> arr = new ArrayList<>(); // 강연 정보를 저장할 리스트

        // 강연 정보 입력
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());  // 강연료
            int d = Integer.parseInt(st.nextToken());  // 강연 가능 날짜

            arr.add(new lecture(m, d)); // 강연 정보 리스트에 추가
            if (d > max) { // 가장 큰 날짜 갱신
                max = d;
            }
        }

        // 최대 수입 출력
        System.out.println(solution(arr));
    }
}

• 강연 정보 입력: 입력으로 주어진 강연료와 가능한 날짜를 객체로 저장하고, 그 정보를 리스트에 담는다.
• 정렬: 가능한 날짜 기준으로 내림차순으로 정렬한다. 이렇게 하면 가장 늦은 날짜부터 탐색할 수 있다.
• 우선순위 큐 사용: 각 날짜에 가능한 강연들 중 가장 높은 보수를 선택하기 위해 우선순위 큐를 사용한다. 큐는 강연료가 높은 순서대로 정렬되어 가장 많은 보수를 받을 수 있는 강연을 선택한다.
• 그리디 알고리즘: 매일 가능한 강연 중에서 가장 높은 보수를 얻을 수 있는 강연을 선택하는 방식으로 문제를 해결한다.