[Java] 코딩테스트에서 Priority Queue 잘 사용하기

 우선순위가 부여된 여러가지 데이터들 중에서 우선순위가 가장 높은 값을 간단하고 효율적이게 얻고 싶을 때 java.util 패키지에서 제공하는 PriorityQueue를 자주 사용한다.

  int와 String같이 자바에서 제공하는 자료형같은 경우에는 특별한 경우가 아닌 이상 Comparator를 따로 설정해줄 필요가 없다. 하지만 내가 정의한 Class를 PriorityQueue에 넣는 경우 Comparator를 사용해서 우선순위를 정해주어야 한다.

  그런데 그 방법이 헷갈려서 이런 상황이 발생할 때마다 구글링을 해서 해결하는데, 매번 구글링하기는 귀찮기 때문에 이번 기회에 블로그에 정리해서 보려고 한다. 블로그에 정리하면서 머릿속에 저장하게 되면 더 좋고~😉

✅ Comparator.comparing 사용하기

1. Class에서 각각의 멤버변수 값을 가져올 수 있는 메서드를 작성한다.
   아래 코드에서는 getFirst(), getSecond(), getThird()가 그 예다.
2. Comparator의 comparing(), thenComparing(), reversed()를 적절히 배치하고 조합해서 원하는 우선순위를 만들어낸다.
   이때 comparing()과 thenComparing()의 인자에는 비교하고자 하는 멤버변수를 넣어준다. (메소드 참조 표현식(::)을 활용)

public class Practice {

    public static void main(String[] args) {

        PriorityQueue<Triple> pq = new PriorityQueue<>(Comparator.comparing(Triple::getFirst).reversed().thenComparing(Triple::getSecond).thenComparing(Triple::getThird));
        pq.offer(new Triple(1, 1, 2));
        pq.offer(new Triple(2, 1, 1));
        pq.offer(new Triple(2, 1, 4));
        pq.offer(new Triple(3, 1, 2));
        pq.offer(new Triple(3, 2, 1));

        while (!pq.isEmpty()) {
            Triple triple = pq.poll();
            System.out.println(triple.first + " " + triple.second + " " + triple.third);
        }
    }
}

class Triple {
    int first;
    int second;
    int third;

    Triple(int first, int second, int third) {
        this.first = first;
        this.second = second;
        this.third = third;
    }

    int getFirst() {
        return first;
    }

    int getSecond() {
        return second;
    }

    int getThird() {
        return third;
    }
}

🚨 주의할 점 🚨

reversed()는 현재까지 나온 결과를 모두 뒤집는 것이다.
이렇게 말로만 설명하면 이해하기 어려우니 예제를 통해 이야기하도록 하겠다.

PriorityQueue<Triple> pq = new PriorityQueue<>(Comparator.comparing(Triple::getFirst).thenComparing(Triple::getSecond).thenComparing(Triple::getThird).reversed());

위는 맨 마지막에 reversed()를 붙인 코드다.
그러면, 현재까지 나온 결과를 모두 뒤집는 것이니 first, second, third에 대해서 모두 내림차순으로 우선순위를 갖게 되는 것이다.

🧐 그렇다면 first는 오름차순, second는 내림차순, third는 오름차순으로 우선순위를 지정하고 싶다면 어떻게 해야할까?

PriorityQueue<Triple> pq = new PriorityQueue<>(Comparator.comparing(Triple::getFirst).reversed().thenComparing(Triple::getSecond).reversed().thenComparing(Triple::getThird));

first 비교에 reversed()를 붙여서 우선 내림차순으로 정렬한 뒤에,
second 비교에 다시 reversed()를 붙여서 first를 내림차순으로 정렬한 걸 뒤집어서 다시 first가 오름차순 정렬되게 만든다. 즉, 앞서 first에 적용한 reversed()를 상쇄시켜 버린 것이다!
그리고 second에 reversed()를 붙였으니 second는 그대로 내림차순으로 정렬될 것이다.

🧐 Comparable를 implements하는 것과 비교해보자.

class Pair implements Comparable<Pair> {
    int first;
    int second;

    Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(Pair o) {
        if (o.first == this.first) {
            return o.second - this.second;
        } else {
            return this.second - o.second;
        }
    }
}

Comparable을 implements해서 비교하는 것은 다음과 같은 특징을 가진다.

1. 코드 작성 시에 헷갈리기 쉽다.
2. 우선순위 규칙을 빠르게 파악하기 어렵다.
3. 좀 더 빠를 수 있다.

이를 종합해봤을 때 앞서 설명한 Comparator.comparing로 구현하면 reversed()를 많이 사용할 경우 뒤집는 시간이 추가되기 때문에 오래걸릴 수 있지만, 코드를 편리하게 작성하고 가독성을 높이는 측면에서는 더 유리할 거 같다.