[Silver-1] 11286번 | 절댓값 힙 | 자바(Java)

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

 

 

위 문제는 "우선순위 큐" 알고리즘으로 힙 자료구조를 구현한다.

우선순위 큐 문제의 최대힙, 최소힙을 풀이하였다면 이 문제도 어렵지 않게 해결할 수 있을 것이다.

(근데 난 바보같이 해결했었음)

 

Java에서는 PriorityQueue, 즉 우선순위 큐 클래스를 지원하기 때문에 이를 사용하겠다.

java.util 패키지 내의 우선순위 큐는 내부적으로 최소 힙(min-heap)을 사용해 자동으로 "오름차순" 정렬된다.

그래서 최대힙의 경우 우선순위 큐를 선언하면서

PriorityQueue<Integer> q = new PriorityQueue<Collections.reverseOreder()>;

 

위와 같이 reverse 정렬을 위한 컬렉션을 사용해서 초기화하면 됐었다.

 

해당 문제에서는 "절댓값 비교"이다.

 

즉, PriorityQueue에서 절댓값이 같은 경우, 원래의 값(부호, 크기)을 고려해서 특정한 순서를 지정해야한다.

이때는, 커스텀 Comparator를 통해 절댓값이 같은 경우, 절댓값이 다른 경우 각각의 정렬 방식을 설정하면 된다.

 

PriorityQueue<Integer> q = new PriorityQueue<>(
    (a, b) -> {
        // 절댓값이 다르면 절댓값 기준으로 정렬
        if (Math.abs(a) != Math.abs(b)) {
            return Integer.compare(Math.abs(a), Math.abs(b));
        }
        // 절댓값이 같으면 원래 값 기준으로 정렬
        return Integer.compare(a, b);
    }
);

 

정렬할 때 Comparator를 애용하자.