[Java] 11286 절댓값 힙

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

입력

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

 

출력

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

 

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int num = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2) -> {
            int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);
            
            if(first_abs == second_abs)
                return o1 > o2 ? 1 : -1;
            else
                return first_abs - second_abs;
        });
        
        for(int i=0; i<num; i++){
            int request = Integer.parseInt(br.readLine());
            
            if(request == 0){
                if(MyQueue.isEmpty())
                    System.out.println("0");
                else
                    System.out.println(MyQueue.poll());
            } else{
                MyQueue.add(request);
            }
        }
    }
}

▶ int num = Integer.parseInt(br.readLine()) : 질의 요청 개수를 사용자로부터 입력 받아 변수 num에 저장함

 

PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2) -> {
    int first_abs = Math.abs(o1);
    int second_abs = Math.abs(o2);

    if(first_abs == second_abs)
        return o1 > o2 ? 1 : -1;
    else
        return first_abs - second_abs;
});

▶ 우선순위 큐 클래스 PriorityQueue를 선언함

▶ Math 클래스의 abs 함수를 사용하여 절댓값을 반환함

▶ 절댓값이 같은 경우 음수를 우선으로 정렬함

▶ 절댓값이 같지 않다면 절댓값을 기준으로 정렬함

 

for(int i=0; i<num; i++){
    int request = Integer.parseInt(br.readLine());

    if(request == 0){
        if(MyQueue.isEmpty())
            System.out.println("0");
        else
            System.out.println(MyQueue.poll());
    } else{
        MyQueue.add(request);
    }
}

▶ 질의 요청 개수만큼 반복하며 사용자에게 Integer 값을 입력 받아 request 변수에 저장함

▶ request의 값이 0이고 큐가 비어있을 경우 "0" 출력

▶ request의 값이 0이고 큐가 비어있지 않을 경우 가장 위에 저장된 값 삭제

▶ request의 값이 0이 아닌 경우 큐에 request 값을 추가함