섹션 9 Greedy - 4. 최대 수입 스케쥴(PriorityQueue 응용문제)

문제 설명

현수는 유명한 강연자이다.
총 N개의 기업으로부터 강연 요청이 들어왔다.
각 기업은 강연을 요청할 때, D일 이내에 와서 강연을 해 주면 M만큼의 강연료를 주기로 약속했다.

현수는 하루에 하나의 기업에서만 강연을 할 수 있다.
이때 최대 수입이 되도록 강연 일정을 구성하려 한다.

---

입력 & 출력

• 입력
  • 첫째 줄에 강연 요청 수 N(1 ≤ N ≤ 10,000)이 주어진다.
  • 다음 줄부터 M D가 한 줄씩 주어지며, 총 N줄이 입력된다.
    • M: 강연료
    • D: 마감 기한일 (D일 이내에 강연 가능)
• 출력
  • 현수가 얻을 수 있는 최대 수입을 출력한다.
• 예시 입력
   

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

• 예시 출력
   

150

---

해결 방법

이 문제는 그리디 + 우선순위 큐(PriorityQueue) 를 활용하는 전형적인 스케줄링 문제입니다.

1. 마감일이 늦은 순으로 정렬한다.
2. 날짜를 거꾸로 순회하면서, 해당 날짜에 가능한 강연을 우선순위 큐에 담는다.
3. 큐에는 가장 큰 강연료부터 꺼내기 위해 Collections.reverseOrder()를 사용한다.
4. 매일 하루씩 줄여가며 가장 높은 강연료 하나를 선택해 수입에 더한다.

---

코드 구현

 

package partGreedy;

import java.util.*;

class Lecture implements Comparable<Lecture> {
	public int m, d;
	
	public Lecture(int m, int d) {
		this.m = m;
		this.d = d;
	}
	
	@Override
	public int compareTo(Lecture o) {
		return o.d - this.d; // 마감일 내림차순 정렬
	}
}

public class Problem4 {
	static int n, max = Integer.MIN_VALUE;
	
	public int solution(ArrayList<Lecture> arr) {
		int answer = 0;
		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
		Collections.sort(arr); // 마감일 기준 내림차순 정렬
		
		int j = 0;
		for (int i = max; i > 0; i--) {
			for (; j < n; j++) {
				if (arr.get(j).d < i) break;
				pQ.offer(arr.get(j).m);
			}
			if (!pQ.isEmpty()) answer += pQ.poll(); // 가장 높은 강연료 선택
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Problem4 T = new Problem4();
		Scanner sc = new Scanner(System.in);
		ArrayList<Lecture> arr = new ArrayList<>();
		n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			int m = sc.nextInt();
			int d = sc.nextInt();
			arr.add(new Lecture(m, d));
			if (max < d) max = d; // 최대 마감일 업데이트
		}
		System.out.print(T.solution(arr));
		sc.close();
	}
}

---

코드 설명

 

• Lecture 클래스
  • 강연료 m, 마감일 d 저장
  • 마감일 기준 내림차순 정렬을 위해 compareTo() 오버라이드
• Collections.sort(arr)
  • 마감일이 늦은 순으로 정렬 → 날짜별 강연 탐색에 유리
• PriorityQueue<Integer> pQ
  • 최댓값 우선순위 큐 사용 → 당일 가능한 강연 중 가장 높은 강연료 선택
• 날짜 루프 for (int i = max; i > 0; i--)
  • max일에서 1일까지 거꾸로 하루씩 탐색
  • 해당 날짜까지 가능한 강연들을 큐에 넣고, 가장 높은 금액 하나만 선택
• if (!pQ.isEmpty()) answer += pQ.poll();
  • 하루에 하나만 강연 가능 → 가장 높은 금액 하나만 수입으로 더함

 

---

시간 복잡도 분석

• 정렬: O(N log N)
• 날짜 루프 (1 ~ max일): 최대 10,000번 → 상수로 간주 (O(1))
• 우선순위 큐 삽입/삭제: 각 강연당 한 번씩 → O(N log N)

총 시간복잡도: O(N log N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런