우선순위 큐(Priority Queue) with 백준 1715

우선순위 큐

우선순위 큐 (Priority Queue)는 요소들이 우선순위에 따라 처리되는 자료구조입니다. 기본적으로 큐와 비슷하게 동작하지만, 큐는 FIFO 방식으로 작동하는 반면, 우선순위 큐는 요소들이 삽입된 순서와 상관없이 우선순위가 높은 요소가 먼저 처리됩니다.

 

Java에서 우선순위 큐는 PriorityQueue 클래스를 통해 제공됩니다. 이 클래스는 내부적으로 최소 힙을 사용하여 요소들을 정렬하며, 기본적으로 요소들의 자연 순서(예: 숫자는 오름차순, 문자열은 알파벳 순)로 정렬됩니다. 커스텀 우선순위가 필요하면 Comparator를 사용하여 정의할 수 있습니다.

우선순위 큐 특징

1. 요소를 삽입할 때 우선순위에 따라 자동 정렬됩니다.

2. 기본적으로 최솟값을 먼저 반환합니다.

3. O(1)로 우선순위가 가장 높은 요소를 빠르게 접근하여 확인 가능합니다.

4. 삽입과 삭제는 O(log n)의 시간 복잡도로 처리합니다.

---

기본 사용법 예제

아래는 자연 순서를 사용하는 우선순위 큐의 예제입니다.

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 정수를 저장하는 우선순위 큐 (기본: 오름차순)
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        // 요소 추가
        priorityQueue.add(10);
        priorityQueue.add(5);
        priorityQueue.add(20);
        priorityQueue.add(15);

        // 우선순위 큐 출력 (정렬 상태로 확인 가능)
        System.out.println("우선순위 큐 내용: " + priorityQueue);

        // 우선순위가 가장 높은 요소 제거 및 반환
        while (!priorityQueue.isEmpty()) {
            System.out.println("가장 높은 우선순위 요소: " + priorityQueue.poll());
        }
    }
}

우선순위 큐 내용: [5, 10, 20, 15]
가장 높은 우선순위 요소: 5
가장 높은 우선순위 요소: 10
가장 높은 우선순위 요소: 15
가장 높은 우선순위 요소: 20

Comparator를 사용한 커스텀 우선순위 큐

아래는 내림차순 정렬을 사용하는 우선순위 큐의 예제입니다.

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

public class CustomPriorityQueueExample {
    public static void main(String[] args) {
        // 내림차순 정렬 우선순위 큐
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

        // 요소 추가
        priorityQueue.add(10);
        priorityQueue.add(5);
        priorityQueue.add(20);
        priorityQueue.add(15);

        // 우선순위 큐 출력 (내림차순 정렬 상태)
        System.out.println("우선순위 큐 내용 (내림차순): " + priorityQueue);

        // 우선순위가 가장 높은 요소 제거 및 반환
        while (!priorityQueue.isEmpty()) {
            System.out.println("가장 높은 우선순위 요소: " + priorityQueue.poll());
        }
    }
}

우선순위 큐 내용 (내림차순): [20, 15, 10, 5]
가장 높은 우선순위 요소: 20
가장 높은 우선순위 요소: 15
가장 높은 우선순위 요소: 10
가장 높은 우선순위 요소: 5

---

백준 1715문제: 카드 정렬

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

package BaekJoon.Greedy;

import java.util.PriorityQueue;
import java.util.Scanner;

public class ex1715 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Long> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            pq.add(sc.nextLong());
        }
        long count = 0;
        while (pq.size() > 1) {
            long a = pq.poll();
            long b = pq.poll();
            count += a + b;
            pq.add(a + b);
        }
        System.out.println(count);
    }
}

코드 설명

1. 우선순위 큐를 사용하여 카드 묶음을 정렬합니다.

2. PriorityQueue는 자동으로 오름차순으로 정렬되고, 크기가 가장 작은 두 묶음을 효율적으로 가져올수 있습니다.

3. 카드 묶음의 크기를 입력받아 우선순위 큐에 삽입합니다.

4. 카드 묶음이 하나가 될 때까지 반복합니다.

5. 크기가 가장 작은 두 묶음을 a, b를 poll()로 가져옵니다.

6. poll()은 첫번째 값을반환하고 제거합니다. 비어있으면 null을 반환합니다.

7. 이 두 묶음을 합친 후, 비교 횟수를 더합니다. 

8. 새로 합친 묶음을 다시 PriorityQueue에 삽입합니다.

 

끝.