[백준] 1655. 가운데를 말해요 (Kotlin)

문제

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

1655번: 가운데를 말해요

 

풀이

0. 문제 해석

하나의 우선순위큐를 활용하여 그 큐의 가운데만큼 pop하고 offer 하는 과정을 반복하면

결과를 구할 수 있지만, 이 과정은 매우 비효율적으로 

 

시간초과가 발생한다.

 

해결방법을 모색해보다가 

https://dragon-h.tistory.com/6

님의 글을 참고하였다.

 

1. 내림차순 우선순위 큐(MaxHeap) , 오름차순 우선순위 큐(MinHeap) 2개 선언
2. 입력을 받을때마다 Max,Min Heap 번갈아가며 삽입
3. 삽입시 MinHeap의 최솟값 > MaxHeap의 최댓값이 되도록 swap
4. MaxHeap의 최댓값이 중간값

 

핵심은 하나는 내림차순, 하나는 오름차순으로 하여 가장 큰값, 가장 작은 값을 빠르게 비교하는 것이다.

 

1. 전체 코드

// [백준] 1655. 가운데를 말해요 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

var n = 0
val maxHeap = PriorityQueue<Int>(Collections.reverseOrder())
val minHeap = PriorityQueue<Int>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    n = readLine().toInt()
    val sb = StringBuilder()

    for(i in 0 until n){
        val cur = readLine().toInt()

        if(maxHeap.size == minHeap.size){
            maxHeap.offer(cur)
        }
        else{
            minHeap.offer(cur)
        }
        if (!minHeap.isEmpty() && !maxHeap.isEmpty()) {
            if (minHeap.peek()!! < maxHeap.peek()!!) {
                // 균형 맞추기 위해 swap
                val tmp = minHeap.poll()
                minHeap.offer(maxHeap.poll())
                maxHeap.offer(tmp)
            }
        }
        sb.append("${maxHeap.peek()!!} \n")
    }

    println(sb)
}

 

 

참고

https://dragon-h.tistory.com/6