[BOJ/백준][Silver1] 11286 : 절댓값 (Kotlin)

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

11286번: 절댓값 힙

 

 

 

[난이도] Silver1
[유형] 우선순위큐

[풀이]
maxHeap, minHeap 두가지를 이용하면 답을 구할 수 있습니다.
pair(abs(x),x) 를 저장하는 Heap 한개로도 문제를 풀수 있습니다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
const val mxN = 1 shl 31
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>{a,b->b.compareTo(a)}
    repeat(readLine().toInt()){
        val v = readLine().toInt()
        when{
            v==0->{
                var ret=0
                if(!minHeap.isEmpty() || !maxHeap.isEmpty()){
                    ret = when {
                        minHeap.isEmpty() -> maxHeap.poll()
                        maxHeap.isEmpty() -> minHeap.poll()
                        else -> if(abs(minHeap.peek()) < abs(maxHeap.peek())) minHeap.poll() else maxHeap.poll()
                    }
                }
                println(ret)
            }
            v<0 -> maxHeap.add(v)
            else -> minHeap.add(v)
        }
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/11286.cpp