[Java] 우선순위 큐 (PriorityQueue) 기본 사용법부터 객체 다루는 방법까지

 

 

우선순위 큐 (PriorityQueue) 란?

---

우선순위 큐는 삽입 순서와 상관 없이, 우선순위가 높은 데이터가 먼저 빠져 나가는 자료구조이다.

 

 

 

PriorityQueue  기본 사용법

---

선언하기

// 우선순위가 낮은 숫자(작은 숫자)가 먼저 추출됨
PriorityQueue<Integer> pQ = new priorityQueue<>();

// 우선순위가 높은 숫자(큰 숫자)가 먼저 추출됨
PriorityQueue<Integer> pQ = new priorityQueue<>(Collections.reverseOrder());

 

 

메서드

삽입

-  add(원소)  : 원소를 추가한다. 

-  offer(원소) : 원소를 추가한다.

 

삭제

-  remove()  : 우선순위의 첫번째 값을 제거하고, 해당 값을 반환한다. 비어있으면 에러가 반환한다.

-  poll()  : 우선순위의 첫번째 값을 제거하고, 해당 값을 반환한다. 비어있으면 null을 발생한다.

 

조회

-  peek()  : 우선순위의 첫번째 값을 반환한다.

 

기타

-  isEmpty()  : 우선순위 큐가 비어있으면 true, 그렇지 않으면 false를 반환한다.

-  clear()  : 우선순위 큐의 요소들을 모두 제거한다. (초기화)

-  size()  : 우선순위 큐의 크기(원소의 개수)를 반환한다.

 

 

PriorityQueue로 객체 다루기

---

위에서는 정수형을 우선순위 큐에 넣고 꺼낼 때의 사용 방법에 대해서 알아보았다. 

 

그렇다면 만약 객체를 우선순위 큐에 넣고 꺼내고 싶다면, 어떻게 해야할까?

 

 

[문제]

학생 객체가 이름, 수학 점수, 영어 점수를 가지고 있으며, 우선순위는 다음과 같이 결정된다.

수학 점수가 높은 학생이 우선순위가 높다.
수학 점수가 같은 경우, 영어 점수가 낮은 학생이 우선순위가 높다.
영어 점수가 같으면, 이름이 사전 순으로 앞에 오는 학생이 우선순위가 높다.

 

 

Comparable 인터페이스와 compareTo() 메서드

class Student implements Comparable<Student> {
    String name;
    int mathScore;
    int englishScore;

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

    @Override
    public int compareTo(Student other) {
        // 수학 점수를 먼저 비교
        if (this.mathScore != other.mathScore) {
            // 수학 점수가 다르면 내림차순 정렬
            return other.mathScore - this.mathScore;
        }
        
        // 수학 점수가 같으면 영어 점수를 비교
        if (this.englishScore != other.englishScore) {
            // 영어 점수가 다르면 오름차순 정렬
            return this.englishScore - other.englishScore;
        }
        
        // 수학 점수와 영어 점수가 같으면 이름을 비교
        return this.name.compareTo(other.name);
    }
}

 

compareTo() 메서드

compareTo()는 Comparable 인터페이스를 구현한 클래스에서 정의된다.

 

compareTo()의 반환값

compareTo()의 반환값은 정수이다.

- this 객체 < other 객체 : 음수 반환

- this 객체 == other 객체 : 0 반환

- this 객체 > other 객체 : 양수 반환

 

그리고 이 반환값에 따라서 객체의 위치가 결정되는 것이다.

음수가 반환되면 this 객체가 other보다 앞에 위치하게 되고, 양수가 반환되면 this 객체가 other 보다 뒤에 위치하게 되는 것이다.

 

✏️ 오름차순 정렬 : this - other
✏️ 내림차순 정렬 : other - this

 

 

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Student> students = new PriorityQueue<>();
        
        students.add(new Student("Alice", 90, 80));
        students.add(new Student("Bob", 80, 90));
        students.add(new Student("Charlie", 90, 70));
        students.add(new Student("David", 80, 80));

        // 결과 출력
        while (!students.isEmpty()) {
            Student student = students.poll();
            System.out.println(student.getName() + " - Math: " + student.getMathScore() + ", English: " + student.getEnglishScore());
        }
}

 

students.add()로 PriorityQueue에 요소를 추가하면, PriorityQueue가 내부적으로 요소를 우선순위에 따라 정렬한다. 이때 우선순위는 Student 클래스에서 정의한 compareTo() 메서드에 의해 결정되는 것이다.

 

 

 

💡 Comparator vs. Comparable

객체를 비교하기 위한 인터페이스로 comparator도 있다. 위의 코드를 보면 알 수 있듯이, comparable은 객체 내부에 비교 기준을 정의하여 다른 객체와 비교한다. 반면, comparator는 객체 외부에서 두 객체를 비교한다.

comparator는 유연성과 재사용성 측면에서 더 우수하지만, comparable는 직관적이고 가독성이 좋다.

따라서, 코딩테스트에서는 직관적이고 가독성 좋은 comparable을 사용하는 것이 효과적이다.

 

 

 

Reference

---

https://kbj96.tistory.com/49

[JAVA] PriorityQueue 우선순위 큐 사용법