[백준] 스택, 큐 - 11286_절댓값 힙 Java[자바]

 

이번 문제는 우선순위 큐를 이용하는 문제이다.

 

Comparable과 Comparator라는 인터페이스가 있다.

 

이 두 개의 인터페이스는 두 값을 비교해 어떠한 기준으로 정렬을 시키는 인터페이스이다.

 

그래서 이 인터페이스를 이용하여 정렬을 한 후 큐에서 poll() 메소드를 사용하면 된다.

 

필자는 Comparator라는 인터페이스를 사용했는데 compare라는 메소드를 오버라이딩하여 사용하면 된다.

 

우리가 생각해야할 기준은 두 가지이다.

 

먼저 절댓값이 서로 다를 때.

 

절댓값이 서로 다르면 어느 하나의 절댓값이 더 크다는 소리다.

 

절댓값이 더 큰 수가 뒤로 배치되어야 한다.

 

절댓값이 같으면 원래의 수가 더 작은 것이 앞에와야한다.

 

이 두가지를 생각하고 로직을 짜면 된다.

 

아래 코드를 보자.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {

                int abs1 = Math.abs(o1);
                int abs2 = Math.abs(o2);
                if(abs1 > abs2) {
                    return abs1 - abs2;
                } else if(abs1 == abs2) {
                    return o1 - o2;
                } else {
                    return -1;
                }
            }
        });

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