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

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

11286번: 절댓값 힙

---

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

public class Main {
    static int N, x;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        //{원본 값, 절댓값}
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] < o2[1]) return -1;
                else if(o1[1] > o2[1]) return 1;
                else {
                    if(o1[0] < o2[0]) return -1;
                    else if(o1[0] > o2[0]) return 1;
                }
                return 0;
            }
        });
        while (N-- > 0) {
            x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(pq.isEmpty()) sb.append("0\n");
                else sb.append(pq.poll()[0]).append("\n");
                continue;
            }
            pq.add(new int[]{x, Math.abs(x)});
        }
        System.out.println(sb);
    }
}

💡 우선순위 큐

풀이

• 절댓값 힙 연산 종류
  • x (x != 0) : 배열에 정수 x 를 넣는다
  • 0 : 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거해 출력 (비어있는 경우 0 출력)
    • 비교 순위 (1) 절댓값 기준 오름차순 (2) 원본 기준 오름차순
• 주어지는 정수 변수형은 int
• 원래 값, 절댓값 2가지로 저장 한 뒤, 순위는 절댓값으로 판별