[백준 2024/01/27] 11286번 절댓값 힙

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

11286번: 절댓값 힙

 

1. 접근 방법

이번 문제는 음수 값을 저장할 heap과 양수 값을 저장한 heap을 따로 2개 만들어주었다.

이후 값을 출력할 때 음수 heap의 peek과 양수 heap의 peek를 꺼내와서 비교해준 후,

 

절댓값이 더 작은 것을 출력해주었다.

만약 절댓값이 같다면 음수heap의 값을 출력해주었다.

만약, 한쪽 heap이 비어있는 경우엔, 비어있지 않은 곳의 heap을 출력해주었다.

둘다 비어있다면, 0을 출력해주었다.

 

2개의 priorityQueue를 선언해줄 때, 유의해아할 점이 있다.

minus heap 에서 -1 -2를 저장하게 된다면 배열이 어떻게 구성이 될까?

[ -2 -1] 이다. 하지만 우리는 [-1 -2] 로 구성이 되어야만이 제대로 plusHeap과 비교해줄 수 있다.

 

 

따라서 minusHeap의 같은 경우엔 Collections.reverseOrder() 를 이용하여

maxHeap으로 구성해주었다.

 

2. 코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Comparator;

public class b11286 {
    public static void main(String[] args) throws IOException {

        PriorityQueue<Integer> minusHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> plusHeap = new PriorityQueue<>();

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();
        int num = Integer.parseInt(line);
        for (int i=0; i<num; i++) {
            int new_num = Integer.parseInt(reader.readLine());

            if(new_num>0){
                plusHeap.add(new_num);
            }
            else if(new_num<0){
                minusHeap.add(new_num);
                //System.out.println(minusHeap);
            }
            else{
                if(minusHeap.isEmpty() && plusHeap.isEmpty()){
                    System.out.println(0);
                }
                else if(minusHeap.isEmpty()){
                    System.out.println(plusHeap.remove());
                }
                else if(plusHeap.isEmpty()){
                    System.out.println(minusHeap.remove());
                }
                else{
                    if(Math.abs(minusHeap.peek())<=plusHeap.peek()){
                        System.out.println(minusHeap.remove());
                    }
                    else{
                        System.out.println(plusHeap.remove());
                    }
                }

            }


        }
    }

}