알고리즘) 우선순위 큐 개념, 최대 수입 스케쥴(그리디 알고리즘, 우선순위 큐)

Priority Queue

 Java에서는 PriorityQueue라는 클래스를 그대로 사용하면 된다. 이진 트리로 구성되어 있어, $nlog(n)$의 시간만에 가장 우선순위가 높은 요소를 찾아준다. 이 때 우선순위는 그 값이 작을수록 높은 것이 기본이며, 반대로 큰 수가 곧 높은 우선순위로 여겨지려면 Collections.reverseOrder()을 인자로 전달한다.

 예를 들어, 아래와 같이 일련의 수를 우선순위 큐에 넣는 경우를 보면 더욱 이해가 잘 될 것이다.

PriorityQueue<Integer> q = new PriorityQueue();
q.offer(7);
q.offer(3);
q.offer(1);
q.offer(11);

while (!q.isEmpty()) {
	System.out.print(q.poll() + " ");   
}
/*
출력 결과
1 3 7 11
*/

반대로 값이 클 수록 우선순위가 높은 것으로 여겨지게 하는 경우도 보자.

PriorityQueue<Integer> q = new PriorityQueue(Collections.reverseOrder());
q.offer(7);
q.offer(3);
q.offer(1);
q.offer(11);

while (!q.isEmpty()) {
	System.out.print(q.poll() + " ");   
}
/*
출력 결과
11 7 3 1
*/

 

객체를 우선순위큐에 넣는 경우

 이 객체의 클래스는 인스턴스간에 비교가 가능하도록 Comparable 인터페이스를 구현해야 한다. 이로 인해서 필수적으로 구현해야 하는 메서드가 compareTo()이다. 이 compareTo 내부에서는 값이 낮을 수록 우선순위가 높도록 하기 위해선 해당 인스턴스의 특정 멤버 변수 값에서 인자로 들어온 인스턴스의 멤버 변수 값을 빼고 역순으로 하기 위해선 반대로 인자로 들어온 인스턴스의 멤버 변수 값에서 해당 인스턴스 멤버 변수 값을 뺀 결과를 반환한다.

public class Main {
	static class Item {
    	int a;
        int b;
        
        public Item(int a, int b) {
        	this.a = a;
            this.b = b;
        }
        
        public int compareTo(Item i) {
        	return this.a - i.a; // a의 값으로 우선순위를 매기며, a의 값이 낮을 수록 우선순위가 높다.
        }
    }
    
	public static void main(String[] args) {
    	PriorityQueue<Item> q = new PriorityQueue();
        // 값이 클수록 우선순위가 높도록 하기 위해선 아래와 같이 우선순위 큐를 정의한다.
        // PriorityQueue<Item> q = new PriorityQueue(reverseOrder());
        q.offer(new Item(5, 3));
        q.offer(new Item(7, 4));
        q.offer(new Item(2, 3));
        
        while (!q.isEmpty()) {
        	Item item = q.poll();
        	System.out.print(item.a + " " + item.b);
        }
    }
}

/*
출력 결과
2 3
5 3
7 4
*/

 

예제(최대 수입 스케쥴)

 N개의 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해주면 M만큼의 강연료를 주기로 했다. 가장 많은 돈을 벌 수 있도록 스케쥴을 짜야 한다. 첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

풀이 ✨

 M을 기준으로 내림차순한 배열을 만든다. 가장 큰 M값을 미리 별도의 변수값으로 할당해둔다. 정렬한 배열의 요소들을 가지고 루프를 돌리는데, 이전에 할당해두었던 최대 M값의 변수 값을 1씩 낮추면서 PriorityQueue에 자신의 M값이 해당 변수 값과 일치하는 요소들을 넣고, 이 중 가장 비용(D)이 비싼 요소를 루프를 돌 때마다 꺼낸다.

작성 코드

import java.util.*;

// 최대 수입 스케쥴
public class Main {
    static class Lecture implements Comparable<Lecture> {
        int m; // money
        int d; // date

        public Lecture(int m, int d) {
            this.m = m;
            this.d = d;
        }

        @Override
        public int compareTo(Lecture l) {
            return l.d - this.d;
        }
    }

    public int solution(int max, List<Lecture> list) {
        int sum = 0, j = 0; // j의 값을 기억하도록 for문 밖에서 정의
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder()); // sort처럼 reverseOrder 메서드 전달로 역순 우선순위 큐 생성 가능
        for (int i = max; i > 0; i--) { // priority queue
            for (; j < list.size(); j++) { // list 순회
                if (list.get(j).d < i) break;
                if (list.get(j).d == i) q.offer(list.get(j).m);
            }
            if (!q.isEmpty()) {
				  
			
                int tmp = q.poll();
                sum += tmp;
            } else break;
        }
		    return sum;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Lecture> list = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int m = sc.nextInt();
            int d = sc.nextInt();
            list.add(new Lecture(m, d));

            max = Math.max(max, d);
        }

        Collections.sort(list);
		System.out.println(main.solution(max, list));
    }
}