[JAVA] 백준 11286번: 절댓값 힙

 

---

문제

• 정수 x 가 주어지고, x가 0이 아닐 때, x를 배열에 저장한다.
• x가 0일 때는, 배열에서 절댓값이 가장 작은 값을 출력하고, 배열에서 제거한다.(절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력한다.)
• N개의 연산이 주어질 때, 연산을 수행한 결과를 출력하는 문제.

 

아이디어

• 자바의 우선순위 큐를 사용해 절댓값 힙을 구현한다.
• 우선순위 큐를 선언하고, 이 큐의 정렬 기준을 comparator를 오버라이딩하여 변경한다.

 

풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 우선순위 큐 선언 후, comparator 오버라이딩
        PriorityQueue<Integer> pQueue = new PriorityQueue<>((n1,n2)->{
            // 절댓값이 같다면 내림차순으로 정렬
            if(Math.abs(n1) == Math.abs(n2)) {
                return n1-n2;
            }
            // 절댓값의 내림차순으로 정렬
            return Math.abs(n1)-Math.abs(n2);
        });

        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(br.readLine());
            // 출력하라는 명령이면(0) 큐가 비어있는지 체크 후 출력
            if(num == 0) {
                sb.append(pQueue.isEmpty() ? 0 : pQueue.remove()).append('\n');
                continue;
            }
            // 입력하라는 명령이면 우선순위 큐에 입력
            pQueue.add(num);
        }
        System.out.println(sb);
    }
}

 

채점 결과

11286번 채점 결과

 

문제 링크

• 11286번: 절댓값 힙 (acmicpc.net)