백준 #1655 #Kotlin #가운데를 말해요

가운데를 말해요

이 문제는 우선순위 큐를 사용하는 문제라고 돼있는데
이분탐색을 통해 간단하게 풀 수 있다.

fun main() {

    val br = System.`in`.bufferedReader()

    val n = br.readLine().toInt()

    val list = arrayListOf<Int>()
    val sb = StringBuilder()

    fun addNum(num: Int) {
        var l = 0
        var r = list.size - 1

        while (l <= r) {
            val mid = (l + r) / 2
            if (list[mid] < num) {
                l = mid + 1
            } else if (list[mid] > num) {
                r = mid - 1
            } else {
                l = mid
                break
            }
        }

        list.add(l, num)
    }

    repeat(n) {
        addNum(br.readLine().toInt())
        sb.append(list[(list.size - 1) / 2]).append('\n')
    }

    print(sb.toString())
}