백준 11286번
https://www.acmicpc.net/problem/11286

문제

---

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

생각하기

---

• 우선순위 큐를 사용한다.
• Comparator를 사용하면 해결 할 수 있다.
• 2값의 절댓값을 비교해서 서로 같은 값일 경우, 절댓값 변환전으로 다시 가서 비교한다.
• 절댓값이 다를 경우, 그냥 두 값의 차이를 준다.

동작

PriorityQueue 자료구조가 핵심이다.

		PriorityQueue<Integer> pque = new PriorityQueue<>((o1, o2) -> {
			int abs1 = Math.abs(o1);
			int abs2 = Math.abs(o2);
			
			if(abs1 == abs2) return o1 - o2;
			return abs1 - abs2;
		});
 

pque에 값이 삽입되면 바로 정렬을 한다.

정렬은 음수 양수 기준으로 정렬한다. 0일 경우, 같은 값일 경우 정렬을 할 필요가 없다.

o1, o2의 2값을 비교할 때 먼저 절댓값으로 변환하고, 절댓값이 같을 경우, 같은 값 내에서 음수 양수로 구분을 하기 위해서 기존의 o1, o2로 다시 비교한다.

o1 - o2를 하여 양수 값일 경우 o1이 크므로 default 오름차순 정렬로 자리를 변경한다.
o1 - o2 의 값이 음수 일 경우, 오름차순이 정렬되어 있으므로 그대로 둔다.

쉽게 설명하자면, 2개의 값을 뺀 값으로 비교를 해서 뺀 값을 양수와 음수로 구분으로 하여 정렬을 진행하는 메커니즘이다.

코드

---

Java

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		PriorityQueue<Integer> pque = new PriorityQueue<>((o1, o2) -> {
			int abs1 = Math.abs(o1);
			int abs2 = Math.abs(o2);
			
			if(abs1 == abs2) return o1 - o2;
			return abs1 - abs2;
		});
		
		
		int N = Integer.parseInt(br.readLine());
		while(N-->0) {
			int x = Integer.parseInt(br.readLine());
			
			if(x != 0) pque.offer(x);
			else {
				if(pque.isEmpty()) sb.append(0).append('\n');
				else sb.append(pque.poll()).append('\n');
			}
		}
		
		bw.write(sb.toString()); bw.flush(); bw.close();
	} // End of main
} // End of Main class

Kotlin

import java.util.*
import java.io.*
import kotlin.math.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()

    val pque = PriorityQueue<Int>( Comparator { o1, o2 ->
        var abs1 = abs(o1)
        var abs2 = abs(o2)
        // 두 값의 값이 같을 경우, 부호를 비교해서 오름차순으로 정렬.
        // 두 값이 다를 경우, 그냥 절댓값에서 숫자의 크기로 비교해서 오름차순으로 정렬
        when {
            abs1 == abs2 -> o1 - o2
            else -> abs1 - abs2
        }
    })

    var N = br.readLine().toInt()
    while(N-->0) {
        var x = br.readLine().toInt()
        if(x != 0) pque.offer(x)
        else {
            if(pque.isEmpty()) sb.append(0).append('\n')
            else sb.append(pque.poll()).append('\n')
        }
    }

    bw.write(sb.toString()); bw.flush(); bw.close()
} // End of main