그리디 알고리즘 섹션 - (2)

그리디 알고리즘 섹션 - (2)

🟪 PriorityQueue 우선순위 큐

• 일반적으로 스택은 LIFO 후입선출 구조를 갖고, 큐는 FIFO 선입선출 구조를 갖는다.
• 그 중에서도 우선순위 큐의 경우, 들어온 순서와는 상관없이 우선순위가 높은 요소를 먼저 처리하는 자료구조이다.

🟪 ‘자바’의 우선순위 큐 라이브러리 사용법

• 기본적으로 PriorityQueue를 생성하면 우선순위 낮은 순으로 객체가 생성되는데 , 그 역순으로 (우선순위 높은 순) 으로 생성하려면 생성 인자로 Collections.reverseOrder() 를 주면 된다.

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

• Priority Queue 값 추가 | add() , offer()
• Priority Queue 값 삭제 | clear() , remove()
• Priority Queue 값 꺼내기 | poll()
• Priority Queue 에서 우선순위 가장 높은 값 출력 | peek()

---

9-4. 최대 수입 스케줄 (PriorityQueue 응용 문제)

설명

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

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

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

입력

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

출력

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

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

/* 9-4. 최대 수입 스케줄 (PriorityQueue) */ 
class Lecture implements Comparable<Lecture>{
    public int money;
    public int time;
    Lecture(int money, int time){
        this.money = money;
        this.time = time;
    }
    @Override
    public int compareTo(Lecture o) {
        return o.time - this.time; //시간 기준 내림차순 정렬 
    };
}

public class Main1 {
    static int n, max = Integer.MIN_VALUE;
    //솔루션
    public int solution(ArrayList<Lecture> arr) {
        int answer = 0;
        //생성 시 COllections.reverseOrder() 하면 우선순위 높은 순으로 객체 저장된다. 
        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) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb=  new Scanner(System.in);
        n = kb.nextInt();
        ArrayList<Lecture> arr = new ArrayList<>();
        for(int i =0; i<n; i++) {
            int m = kb.nextInt();
            int d = kb.nextInt();
            arr.add(new Lecture(m, d));
            if(d>max) max = d; //일단 최대 날짜값을 담아주고 
        }
        System.out.println(T.solution(arr));    
    }
}

---