[Inflearn] 자바 알고리즘 문제풀이 #09-04 4. 최대 수입 스케쥴(PriorityQueue 응용문제)

문제

설명

현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.

각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.

단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

 

입력 

첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.

 

출력 

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

예시 입력 1 

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

 

예시 출력 1

150

 

 

 

 

선생님 풀이

package Main9;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

class Lecture implements Comparable<Lecture> {
    public int money;
    public int date;
    Lecture(int money, int date){
        this.money = money;
        this.date = date;
    }
    @Override
    public int compareTo(Lecture o) {
        return o.date - this.date;
    }
}

public class Main9_4 {
    static int n, max=Integer.MIN_VALUE;
    public int Solution(ArrayList<Lecture> arr) {
        int answer=0;
        Collections.sort(arr);
        // PriorityQueue<Integer> pQ = new PriorityQueue<>(); 기본 : 작은값 꺼냄
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
        int j=0;
        for(int i=max; i>0; i--) {  //date값이 max값부터 1까지 접근
                                    //(60, 5), (50, 3)처럼 date값 사이 비어있을 경우까지 고려한 방법
            for(; j<n; j++) { //arr에 순차적으로 접근
                if(arr.get(j).date<i) break;
                pQ.offer(arr.get(j).money); //현재 max보다 크거나 같은 값들만 offer()
            }
            if(!pQ.isEmpty()) answer += pQ.poll();
        }
        return answer;
    }

    public static void main(String[] args){
        Main9_4 T = new Main9_4();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        ArrayList<Lecture> arr = new ArrayList<>();
        for(int i=0; i<n; i++) {
            int m = sc.nextInt();
            int d = sc.nextInt();
            arr.add(new Lecture(m, d));
            if(d>max) max=d;
        }
        System.out.println(T.Solution(arr));
    }
}

priority queue 구현은 처음이기도 했고, 앞서 탐욕 알고리즘(greedy)으로 풀어내려 해봤지만

"정렬 후 특정 범위에 있는 것들 중 최대의 money값을 갖는 것"을 뽑는 로직을 만들기가 힘들었다.

하지만 요런 기능을 대신 해주는 우선순위 큐를 알게 되었다! Collections.reverseOrder() 같이 기억해두자!

 

 

 

결과

 

 

 

알게된 점

1. 우선순위 큐(Priority Queue)

PriorityQueue<Integer> pQ = new PriorityQueue<>();

기본 설정은 poll() 했을 때 pQ에 담겨있는 값들 중 가장 작은 값이 반환된다.

 

PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

Collections.reverseOrder() 설정으로 poll() 했을 때 pQ에 담겨있는 값들 중 가장 큰 값을 반환하게 만들어 줄 수 있다.