04: 우선순위 큐

우선순위 큐

---

Java에서 우선순위 대기열을 구현하려면 우선순위 대기열 데이터 구조의 내장 구현인 java.util.PriorityQueue 클래스를 사용할 수 있습니다. PriorityQueue 클래스는 Java Collections Framework의 일부이며 우선순위 큐의 힙 기반 구현을 제공합니다.

import java.util.PriorityQueue;
import java.util.Comparator;

우선 순위 대기열은 자연 순서(Comparable 인터페이스를 구현하는 경우) 또는 사용자 정의 비교기를 사용하여 요소를 정렬합니다. 사용자 지정 주문을 정의하려면 Comparator 구현을 만들어야 합니다. 우선 순위 대기열에 저장하려는 요소가 사용자 정의 클래스인 경우 해당 클래스에서 Comparable 인터페이스를 구현하거나 사용자 정의 비교기를 제공해야 합니다.

 

 

우선 순위 대기열 개체를 생성합니다.

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

 

 

사용자 지정 비교기를 사용하려면 PriorityQueue 생성자에 대한 인수로 전달할 수 있습니다.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(descendingComparator);

 

 

add() 또는 offer() 메서드를 사용하여 우선순위 대기열에 요소를 추가할 수 있습니다. 요소는 비교기 또는 자연 순서에 의해 정의된 우선순위에 따라 삽입됩니다.

priorityQueue.add(5);
priorityQueue.offer(3);

 

 

우선 순위 대기열에서 요소를 제거합니다. 우선순위 큐에서 요소를 제거하려면 remove() 또는 poll() 메서드를 사용할 수 있습니다. 이 메서드는 우선 순위가 가장 높은 요소를 제거하고 반환합니다.

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

 

 

제거하지 않고 우선순위가 가장 높은 요소에 접근하고 싶다면 peek() 메서드를 사용할 수 있습니다. 우선 순위 큐가 비어 있으면 우선 순위가 가장 높은 요소 또는 'null'을 반환합니다.

int highestPriorityElement = priorityQueue.peek();

 

 

.isEmpty() 메서드를 사용하여 우선 순위 큐가 비어 있는지 확인할 수 있습니다.

boolean isQueueEmpty = priorityQueue.isEmpty();
System.out.println("Is the priority queue empty? " + isQueueEmpty);

 

 

Java의 'PriorityQueue'에 값을 삽입하면 자연 순서 또는 사용자 지정 비교기에 의해 정의된 순서에 따라 자동으로 오름차순 정렬됩니다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(5);
        pq.add(2);
        pq.add(8);
        pq.add(3);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); 
        }
    }
}

출력 결과

2
3
5
8

 

 

다음은 정수를 내림차순으로 정렬하는 사용자 지정 비교기의 예입니다.

우선 순위 대기열은 자연 순서(Comparable 인터페이스를 구현하는 경우) 또는 사용자 정의 비교기를 사용하여 요소를 정렬합니다. 사용자 지정 주문을 정의하려면 Comparator 구현을 만들어야 합니다. 우선 순위 대기열에 저장하려는 요소가 사용자 정의 클래스인 경우 해당 클래스에서 Comparable 인터페이스를 구현하거나 사용자 정의 비교기를 제공해야 합니다.

Comparator<Integer> descendingComparator = new Comparator<Integer>() {
    public int compare(Integer a, Integer b) {
        return b - a; 
    }
};

---

예제1: N번째 큰 수

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

 

N번째의 큰 수 구하기 → 가장 아랫줄에서 가장 작은 값을 출력하면 답이 나온다.

접근

1. 우선순위 큐에 값을 삽입하면 자동으로 오름차순 정렬된다. 따라서 N^2개의 값을 넣었을 때 가장 위의 값을 peek()으로 출력하면 전체 값 중 가장 작은 값이 출력된다.
2. N개 중에서 가장 작은 값을 출력해야 하므로, 맨 처음에 값을 N개만 삽입한다.
3. 나머지 값을 넣을 때는 peek() 보다 큰 값인 경우에 현재 peek()을 제거하고 해당 값을 삽입한다.
4. 이 과정을 반복하면 마지막에 peek()한 값이 전체에서 N번째로 큰 수가 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            pq.add(num);
        }

        for (int i = N; i < N * N; i++) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            int num = Integer.parseInt(st.nextToken());
            if (num > pq.peek()) {
                pq.poll();
                pq.add(num);
            }
        }

        System.out.println(pq.peek());
    }
}

 

예제2: 카드 정렬하기

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

접근

1. 10 20 40이 있는 경우 가장 작은 값이 나오는 경우는 오름 차순 순서대로 더하는 것이다.
2. (10+20) + (10+20) + 40 = 100
3. 두 값을 더한 후에 한번 더 전체 총합에서 더해지는 것을 확인할 수 있다.
4. 결국 우선순위 큐로 오름차순 시켜주고, 두 값을 더한 다음 우선순위 큐로 다시 넣어주는 것을 반복해야 한다.

우선 순위 큐: [10, 20, 40]

[40] → pull(10) + pull(20) → answer에 더함 (answer = 30)

pull(10) + pull(20) → [40] 우선순위 큐에 다시 넣기

[30, 40]

[ ] → pull(30) + pull(40) → answer에 더함 (answer = 30 + 70 = 100)

우선순위 큐가 비었으므로 answer 출력

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        PriorityQueue<Long> pq = new PriorityQueue<>();
        long answer = 0;


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            pq.add(Long.valueOf(st.nextToken()));
        }

        while (pq.size() > 1) { // 한번에 두개 뽑으므로 2개 이상 있어야함.
            long temp = pq.poll() + pq.poll();
            answer += temp; // 두 값 더한만큼 전체 총합에 더해주고
            pq.add(temp); // 다시 우선순위에 넣어서 두 번 더해지도록 함.
        }
        System.out.println(answer);
    }
}