[BOJ][우선순위큐] 11286. 절댓값 힙 (java)

✏️ 문제

문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력
입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

 

🔢 알고리즘

 

#자료구조  #우선순위큐

 

 

🤯 풀이 방법

 

우선순위 큐를 사용한다.

이때 절댓값을 기준으로 비교한다고 해도 출력하는 값은 원래 값이어야 하므로 int[]배열을 이용해서 0번 인덱스에는 절댓값, 1번 인덱스에는 원래 값으로 큐에 넣는다.

절댓값이 같은 경우에는 가장 작은 수를 출력해야 하므로 우선순위 기준을 두개 설정한다.

 

👾 구현 코드 (자바)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());

            if (cur == 0) {
                if (q.size() == 0) {
                    System.out.println(0);
                } else {
                    System.out.println(q.poll()[1]);
                }
            } else {
                q.offer(new int[]{Math.abs(cur), cur});
            }
        }

    }
}