[JAVA] 백준 11286 우선순위 큐

 

 

 

 

 

 

 

11286번: 절댓값 힙

문제

절댓값 힙은 절댓값이 가장 작은 숫자를 출력한다. (절댓값이 같다면 작은 값을 먼저 출력)

입력에 0이 주어진다면 값을 출력하고 나머지 값이 들어온다면 값을 절댓값 힙에 넣는다.

(입력이 0이고 힙이 비어있다면 0을 출력)

N번의 값이 주어질 때 값을 출력하시오.

풀이

우선순위 큐는 람다식을 사용하여 만들었다.

이 람다식의 리턴값이 양수라면 첫 번째 값이 크다고 인식하고, 람다식이 음수라면 두 번째 값이 크다고 인식하여 우선순위를 정한다.(작은값이 먼저 나옴)

우선순위 큐를 사용해서 다음과 같은 규칙으로 풀었다.

1. 입력받은 값이 0이 아니라면 큐에 삽입한다.
2. 입력받은 값이 0이고 큐가 비어있다면 0을 출력한다.
3. 입력받은 값이 0이고 큐가 비어있지 않다면 큐에서 값을 삭제하고 출력한다.

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

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

        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) ->{
            int num1 = Math.abs(o1);
            int num2 = Math.abs(o2);

            if(num1 == num2)
                return o1 > o2 ? 1 : -1;
            else
                return num1 - num2;     
        });

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            int c = Integer.parseInt(br.readLine());
            if(c != 0){
                q.add(c);
            }else if(c == 0 && q.isEmpty()) sb.append(0).append("\n");
            else if(c == 0 && !q.isEmpty()) sb.append(q.poll()).append("\n");
        }
        System.out.println(sb);
    }
}

결과