[알고리즘] 우선순위 큐(Priority Queue)

서론

코딩테스트를 준비할 때 스택과 큐를 공부했다면, 그 다음으로 공부해야 할 것은 Priority Queue입니다. 이번 포스트에서는 Priority Queue가 무엇인지, 간단한 구현 예제를 포스트하겠습니다.

---

1. Priority Queue

Priority Queue는 일반적인 Queue와 다르게 들어온 순서가 아닌 요소의 우선순위에 따라 요소를 처리하는 자료구조입니다. 우선순위 큐의 경우 힙 자료구조를 통해서 구현될 수 있습니다. 기본적으로 오름차순으로 정렬되지만, 우선순위를 객체로 직접 정의하여 우선순위를 설정하여 정렬할 수 있습니다.

---

1-1. Priority Queue의 기본 연산

• offer() : 요소를 추가 (우선순위에 따라 정렬)
• poll() : 가장 우선순위가 높은 요소 제거 및 반환
• peek() : 가장 우선순위가 높은 요소 반환(제거 x)
• isEmpty() : 큐가 비어있는지 확인(true or false)
• size() : 큐에 들어 있는 요소의 개수 반환

---

1-2. Priority Queue 예시 코드 (기본형 : 오름차순)

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 기본: 오름차순

        pq.offer(30);
        pq.offer(10);
        pq.offer(20);
        pq.offer(50);
        pq.offer(40);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 10, 20, 30, 40, 50 (작은 값부터)
        }
    }
}

위의 코드를 통해 Priority Queue는 기본적으로 오름차순으로 정렬되는 것을 볼 수 있습니다.

---

1-3. Priority Queue 예제 (내림차순)

기본 동작과 다르게 큰 값이 먼저 나오도록 (내림차순) 우선순위를 설정할 수 있습니다.

import java.util.PriorityQueue;
import java.util.Collections;

public class DescendingPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순 정렬

        pq.offer(30);
        pq.offer(10);
        pq.offer(50);
        pq.offer(20);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 50 → 30 → 20 → 10 (내림차순)
        }
    }
}

---

1-4. Priority Queue (우선순위 설정)

Priority Queue의 꽃인 우선순위를 설정하고, 우선순위에 따라 처리하는 Priority Queue를 구현하는 예제를 적어보겠습니다.

아래 예제는 국어 점수가 높은 순으로 정렬하며, 국어 점수가 같으면 영어점수가 높은 순으로 정렬하는 예제입니다.

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

class Student {
    String name;
    int koreanScore;
    int englishScore;

    public Student(String name, int koreanScore, int englishScore) {
        this.name = name;
        this.koreanScore = koreanScore;
        this.englishScore = englishScore;
    }

    @Override
    public String toString() {
        return name + " (국어: " + koreanScore + ", 영어: " + englishScore + ")";
    }
}

public class StudentPriorityQueue {
    public static void main(String[] args) {
        // Comparator: 국어 점수 내림차순 -> 국어 점수 같으면 영어 점수 내림차순
        PriorityQueue<Student> pq = new PriorityQueue<>((a, b) -> {
            if (b.koreanScore != a.koreanScore) {
                return b.koreanScore - a.koreanScore; // 국어 점수 높은 순
            }
            return b.englishScore - a.englishScore; // 국어 점수 같으면 영어 점수 높은 순
        });

        pq.offer(new Student("김철수", 90, 80));
        pq.offer(new Student("이영희", 95, 85));
        pq.offer(new Student("박지훈", 90, 85));
        pq.offer(new Student("정수민", 80, 90));

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

실행결과

이영희 (국어: 95, 영어: 85)
김철수 (국어: 90, 영어: 80)
박지훈 (국어: 90, 영어: 85)
정수민 (국어: 80, 영어: 90)

---

결론

우선순위 큐는 특정 기준에 따라 요소를 정렬하여 처리해야 할 때 매우 유용한 자료구조입니다. 이번 포스트에서는 국어 점수와 영어 점수를 기준으로 학생을 정렬하는 우선순위 큐를 구현해 보았습니다.

우선순위 큐의 핵심은 Comparator를 활용하여 정렬 기준을 자유롭게 설정할 수 있다는 점입니다. 이를 통해 단순한 숫자 정렬뿐만 아니라 객체의 특정 필드를 기반으로 동적 우선순위를 부여하는 활용도 가능합니다.

이제 여러분도 PriorityQueue를 활용하는 문제를 박살낼 수 있습니다!!