최대 수입 스케쥴 (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

 

 

 

문제 해결

 

우선순위 큐

큐는 먼저 들어오는 데이터가 먼저 나가는 선입선출 (FIFO) 형식의 자료구조지만

우선순위 큐는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조

 

자바에서 PriorityQueue 이렇게 사용하면 됨 (우선순위큐)

우선순위를 큰 값으로 설정하면 현 시점에서 가장 큰 값을 꺼내줌. / 우선순위를 작은 값으로 설정하면 작은 값을 꺼내주고!!

 

class Lecture {
    int fee;
    int day;

    public Lecture(int fee, int day) {
        this.fee = fee;
        this.day = day;
    }
}

• 우선 강의료와 마감일을 담은 Lecture 클래스를 만들어준다.

 

Scanner in = new Scanner(System.in);
int n = in.nextInt();

List<Lecture> lectures = new ArrayList<>();

for (int i = 0; i < n; i++) {
    int fee = in.nextInt();
    int day = in.nextInt();
    lectures.add(new Lecture(fee, day));
}

• 각 강연의 fee와 day를 입력 받아 Lecture 객체로 리스트 lectures에 저장한다.

 

Collections.sort(lectures, (l1, l2) -> l1.day - l2.day);

• 강연을 마감일(day) 기준으로 오름차순 정렬한다.:
  • Lecture(20, 1)
  • Lecture(30, 1)
  • Lecture(50, 2)
  • Lecture(40, 2)
  • Lecture(60, 3)
  • Lecture(30, 3)

 

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

for (Lecture lecture : lectures) {
    pQ.offer(lecture.fee);
    if (pQ.size() > lecture.day) {
        pQ.poll();
    }
}

• 우선순위 큐 pQ를 사용해 현재 가능한 강연료를 저장한다
• 각 강연을 순회하며 강연료를 큐에 추가하고. 큐의 크기가 현재 날짜보다 크면 가장 작은 강연료를 제거해가는 방식으로 진행해간ㄷ다.

•  

 

int maxIncome = 0;
while (!pQ.isEmpty()) {
    maxIncome += pQ.poll();
}

System.out.println(maxIncome);

• 최종적으로 우선순위 큐에 남아있는 강연료를 모두 더합니다.
  • 큐: [40, 50, 60]
  • maxIncome = 40 + 50 + 60 = 150

 

최종 코드

 

import java.util.*;

public class P04_최대수입스케줄_PriorityQueue {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        List<Lecture> lectures = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int fee = in.nextInt();
            int day = in.nextInt();
            lectures.add(new Lecture(fee, day));
        }

        // 마감일 기준 오름차순 정렬
        //Lecture(20, 1)
        //Lecture(30, 1)
        //Lecture(50, 2)
        //Lecture(40, 2)
        //Lecture(60, 3)
        //Lecture(30, 3)
        Collections.sort(lectures, (l1, l2) -> l1.day - l2.day);

        // 우선순위 큐
        PriorityQueue<Integer> pQ = new PriorityQueue<>();

        // 가능한 최대 수입을 계산
        for (Lecture lecture : lectures) {
            pQ.offer(lecture.fee);
            if (pQ.size() > lecture.day) { // 만약 우선순위 큐의 크기가 현재 날짜보다 크면
                pQ.poll(); // 가장 작은 강연료 제거해가기 (해당 날짜만큼 큐에 들어있게)
            }
        }

        // 우선순위 큐에 남아있는 강연료들 더하기
        int maxIncome = 0;
        while (!pQ.isEmpty()) {
            maxIncome += pQ.poll();
        }

        System.out.println(maxIncome);
    }
}

class Lecture {
    int fee;
    int day;

    public Lecture(int fee, int day) {
        this.fee = fee;
        this.day = day;
    }
}