우선순위큐 (PriorityQueue)에 객체 저장하기

탐색문제를 풀다가 우선순위큐를 이용하는 문제들을 만나게 되어서 다음에 만났을 떄는 검색없이 풀고싶어 정리를 하게 되었다.

✨ 우선순위큐는 사용되는 생성자에 따라 우선순위가 정해진다. (우선순위 큐에 Integer 자료형이 저장된다고 했을 때, 기본적으로 숫자가 작을수록 우선순위가 높다.)

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

반대의 순서로 정렬하려면 다음과 같이 함수를 사용해주면 된다.

PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

✨ 탐색문제를 풀다보면 우선순위큐에 객체를 저장하는 경우가 있었다.

• 우선순위큐에 객체를 저장하려면 해당 객체의 클래스는 Comparable 인터페이스를 implements 해야한다.
• 해당 class 내에서 compareTo함수를 override하게 되는데, 이때 작성하는 compareTo 함수내용에 따라 우선순위큐의 우선순위가 정해진다.

//BOJ 6087 풀 때 사용한 class

class Mirror implements Comparable<Mirror>{
    int x, y, cnt, dir;

    Mirror(int x, int y, int cnt, int dir) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.dir = dir;
    }

    @Override
    public int compareTo(Mirror m) {
        return this.cnt - m.cnt;
    }
}

1. 우선순위큐에 저장되는 객체를 위한 클래스(Mirror)는 Comparable을 구현한다.
   • Comparable : Mirror 객체와 다른 Mirror타입의 객체 비교
2. 생성자를 작성하는 것은 다른 클래스들과 다를 바가 없다.
3. 위의 코드의 경우에는 compareTo함수를 override할 떄 cnt를 기준으로해서 오름차순으로 우선순위가 정해진다. (즉, cnt가 작은 객체가 높은 우선순위)

해당객체.some - 비교객체.some => 오름차순
비교객체.some - 해당객체.some => 내림차순