백준 11286 - 절댓값 힙

문제 파악

절댓값 힙을 구현하는 문제!
정수 x를 넣거나 절댓값이 가장 작은 수를 꺼내는 연산을 반복하는 프로그램
만약 x가 0이라면 힙에서 값을 꺼내기
아니면 힙에 값을 넣기

우선순위 큐를 이용해 가장 작은 값을 빠르게 꺼낼 수 있다!
우선순위 큐는 가장 먼저 들어온 값이 먼저 나가는 일반적인 큐와 다르게 우선순위가 가장 높은 값부터 나간다.

우선순위 큐를 쓰는 이유 : 값 삽입과 꺼내기를 반복하면서 절댓값이 가장 작은 값을 찾는 것은 일반 배열로는 매번 정렬이 필요해 비효율적이다.

하지만 우선순위 큐는 자동으로 정렬이 되어 값을 넣을 때 적절한 위치에 바로 넣고 뺄 때는 가장 우선순위가 높은 값을 빼준다.

이 문제에서는 우선순위 큐를 먼저 절댓값 기준으로 정렬을 해 비교하고 만약 절댓값이 같으면 실제 값을 기준으로 정렬을 하는 것이 필요해 우선순위 비교 기준을 커스텀해야 한다.

풀이

1. 첫번째 입력값 n으로 몇 개의 연산을 할 건지 받는다.
2. n개의 값 x들을 입력받는다.
3. 만약 x가 0이면
   a. 큐가 비어있으면 0을 출력한다.
   b. 비어있지 않으면 절댓값이 최소인 값을 출력한다.
   c. 절댓값이 같으면 음수를 먼저 출력한다.
4. x가 0이 아니면 큐에 x를 추가하고 우선순위 큐 정렬 기준으로 자동 정렬한다.

코드

import java.util.PriorityQueue;
import java.util.Scanner;

public class 절댓값_힙 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //몇 개 입력받을 건지
        int n = sc.nextInt();

        //우선순위 큐 정렬 기준 커스텀
        //comparator 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            //비교할 두 매개변수를 절댓값으로 씌워서
            int absA = Math.abs(a);
            int absB = Math.abs(b);

            if (absA == absB) {
                //절댓값 같으면 실제 값 비교
                //음수면 앞이 더 작고 양수면 앞이 더 크다는 것
                return a - b;
            } else {
                //절댓값 비교
                return absA - absB;
            }
        });

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();

            //0이 아니면 추가
            if (x != 0) {
                pq.add(x);
            } 
            else {
                //우선순위 큐가 비어있다면 0 출력
                if (pq.isEmpty()) {
                    System.out.println(0);
                } 
                //우선순위 큐에서 제일 앞에 있는 요소를 꺼내는 메소드
                else {
                    System.out.println(pq.poll());
                }
            }
        }
    }
}