[Greedy Algorithm] 최대 수입 스케쥴(PriorityQueue 응용문제)

 

 

 

설명

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

예시 입력

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

 

 

 

 

예시 출력

150

 

 

 

풀이

[입력]

입력이 들어오면 Lecture 클래스를 담는 ArrayList에 담는다.

입력받을 때 일차(D)의 최댓값을 구해놓는다.

 

[로직]

강연료(M)가 많아야 수입이 크다. 

날짜에 의해 내림차순 정렬을 한다. 그러면 1일차~3일차에 가능한 강연, 1일차~2일차에 가능한 강연, 1일차에 가능한 강연 순으로 나열된다. 날짜에 의한 내림차순 정렬은 Lecutre 클래스에 compareTo 메소드에 구현하고 Collections.sort()를 사용하면 된다.

 

PriorityQueue를 생성한다. 

 

이렇게 사용하면 작은 값을 우선순위로 꺼내고,

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

 

 

이렇게 사용하면 큰 값을 우선순위로 꺼낸다.

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

 

 

수입이 최대여야 하므로 큰 값을 우선순위로 꺼내야 한다.

 

 

날짜를 거꾸로 돌면서 처리한다. 입력받을 때 날짜의 최댓값을 구해놓았다. 해당 날짜부터 거꾸로 반복문을 돈다.

입력받은 강연 수 만큼 또 반복문을 돈다. 날짜가 현재 날짜보다 작으면 PriorityQueue에 값을 넣지 않는다. 즉, 최대 3일차 까지 강연을 할 수 있어서 초기값은 i가 3이다. 그리고 내부 반복문에서, j가 2이면 PriorityQueue에 값을 넣지 않는 것이다. 크거나 같으면 PriorityQueue에 값을 넣는다. (PriorityQueue의 offer 메소드 사용)

 

그리고 PriorityQueue가 비어있지 않다면 어떤 강연을 할 것인지 선택한다. (PriorityQueue의 poll 메소드 사용하면 가장 큰 값을 선택한다.) 그리고 선택된 값을 answer에 누적한다.

 

 

다음 그림은 이해를 돕기 위해 그림으로 나타낸 것이다.

 

 

 

코드

package inflearn._9_4;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Lecture implements Comparable<Lecture> {

    public int money;
    public int time;

    public Lecture(int money, int time) {
        this.money = money;
        this.time = time;
    }

    @Override
    public int compareTo(Lecture o) {
        return o.time - this.time;
    }
}

public class Main {

    static int n, max = Integer.MIN_VALUE;

    public static int solution(ArrayList<Lecture> arr) {

        int answer = 0;
        // PriorityQueue<Integer> pQ = new PriorityQueue<>(); // 작은 값 우선순위
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder()); // 큰 값 우선순위

        Collections.sort(arr); // 날짜에 의해서 내림차순 정렬

        int j = 0;

        for(int i = max; i >= 1; i--) { // 날짜가 하루씩 작아짐
            for (; j < n; j++) {
                if(arr.get(j).time < i) break; // 날짜가 작으면 넣지 않기
                pQ.offer(arr.get(j).money);
            }

            if(!pQ.isEmpty()) answer += pQ.poll(); // 어떤 강연을 할 것이지 선택
        }

        return answer;
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

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

        ArrayList<Lecture> arr = new ArrayList<>();

        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            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;
        }

        bw.write(sb.append(solution(arr)).toString());
        bw.flush();
        bw.close();
        br.close();
    }
}