[백준] 11286번 절댓값 힙(java)

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

11286번: 절댓값 힙

이 문제는 이름에서도 알 수 있듯이 힙 문제이다.

문제자체는 매우 단순하다.

 

핵심

문제를 그대로 해석하면 0이면 절댓값이 작은 수를 반환하고, 0이 아닌 수이면 큐에 넣는 것이다.

우선큐의 Comparator를 재정의하면 쉽게 풀 수 있다.

 

정답 코드

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);
            if(abs1 == abs2) return o1-o2;
            return abs1 - abs2;
        });
        for(int i = 0 ; i < n; i++){
            int val = sc.nextInt();
            if(val == 0){
                if (queue.isEmpty()) sb.append(0).append("\n");
                else sb.append(queue.poll()).append("\n");
            }else queue.add(val);
        }
        System.out.println(sb);
    }
}

해설

문제 그대로 우선큐의 Comparator를 재정의하였다.

절댓값이 작은 순으로 반환하고, 만약 같을 시 더 작은 값을 반환한다. ex) -1 ,1  -> -1

만약 큐가 비어있는데 0이 입력된다면, StringBuilder에는 0을 담는다.

비어있지 않다면, 큐에서 뺀 값을 담는다.

 

 

배운 점

문제를 많이 풀다 보니, Comparator를 재정의하는 것이 쉽게 느껴졌다.

우선 큐의 개념을 알고만 있어도 쉽게 풀 수 있는 문제라고 생각된다.

역시 알고리즘문제는 많이 풀어봐야 실력이 빨리 성장하는 것 같다.