프로그래밍

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

[난이도] Silver2
[유형] 힙

[풀이]
Heap

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val pq = PriorityQueue<Int>{a,b->b.compareTo(a)}
    var N = readLine().toInt()
    repeat(N){
        var v = readLine().toInt()
        when{
            v>0 -> pq.add(v)
            pq.isEmpty() -> println(0)
            else -> println(pq.poll())
        }
    }
}

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

https://www.acmicpc.net/problem/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