[알고리즘]최대 수입 스케쥴(PriorityQueue)

Priority Queue(우선순위 큐)

먼저 들어온 순서대로 데이터가 나가는 것이 아닌, 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조

특징

• 힙을 이용하여 구현하는 것이 일반적이다.
• 힙으로 구성되어 이진트리 구조로 이루어져 있다.
• 힙으로 구성되어 있기 때문에 시간 복잡도는 O(nLogn)이다.

 

참고) Heap(힙)

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리(complete binary tree)를 기본으로 한 자료구조
• 힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 'max heap(최대 힙)', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 'min heap(최소 힙)'이라고 부른다.
• 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

 

 

 

최대로 벌 수 있는 강연 수입을 구하는 프로그램

N개의 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.

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

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

class Lecture implements Comparable<Lecture> {
	int money, day;
	Lecture(int m, int d) {
		this.money = m;
		this.day = d;
	}
	@Override
	public int compareTo(Lecture object) {
		return object.day - this.day; // 날짜 기준 내림차순
	}
}

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<>(Collections.reverseOrder()); // 우선순위 큐 // 내림차순
		Collections.sort(arr); // 정렬

		int j=0;
		for (int i=max; i>=1; i--) {
			for ( ; j<n; j++) {
				if (arr.get(j).day<i) break;
				pQ.offer(arr.get(j).money);
			}
			if (!pQ.isEmpty()) answer += pQ.poll();
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); // 강연을 요청한 기업의 수
		ArrayList<Lecture> arr = new ArrayList<>();
		for (int i=0; i<n; i++) {
			int m = scanner.nextInt(); // 강연료
			int d = scanner.nextInt(); // d일 안에 강연
			arr.add(new Lecture(m, d));
			if (d>max) max = d; // day 최댓값
		}
		System.out.println(solution(arr));
	}

}

---

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