[백준] 2075 - N번째 큰 수

최소 힙 트리를 구현하고 루트 값을 출력하면 되는 문제이다.
다만, Heap 의 사이즈를 5로 제한해야 하기 때문에 사이즈를 체크하고, 루트와 새로운 값의 비교가 이루어져야 한다는 조건이 존재한다.

다른 방법으로는 파라메트릭 서치를 통해 구현하는 방법이 존재한다.
다만, 이 방법은 구현이 복잡하기 때문에 우선순위 큐(최소 힙) 을 사용하는 것을 추천한다.

풀이 1 - 힙

import java.util.PriorityQueue
import java.util.StringTokenizer

fun `2075-N번째 큰 수-Heap`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val heap = PriorityQueue<Int>(n)

    repeat(n){
        val token = StringTokenizer(br.readLine())

        repeat(n){
            val num = token.nextToken().toInt()

            when {
                heap.size >= n && heap.peek() >= num -> {}
                heap.size >= n && heap.peek() < num -> {
                    heap.poll()
                    heap.offer(num)
                }
                else -> heap.offer(num)
            }
        }
    }

    bw.write(heap.peek().toString())
    bw.flush()
    bw.close()
    br.close()
}

풀이 2 - 파라메트릭 서치

fun `2075-N번째 큰 수-Parametric Search`(){
    var result = 0
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    var low = -1_000_000_000
    var high = 1_000_000_000
    val arr = Array(n){
        val token = StringTokenizer(br.readLine())
        IntArray(n){ token.nextToken().toInt() }
    }

    while (low <= high){
        var count = 0
        val mid = low + (high - low) / 2

        loop@
        for(j in 0 until n){
            var iLow = 0
            var iHigh = n - 1
            var firstIndex = n

            while (iLow <= iHigh) {
                val iMid = iLow + (iHigh - iLow) / 2

                if (arr[iMid][j] >= mid) {
                    firstIndex = iMid
                    iHigh = iMid - 1
                } else {
                    iLow = iMid + 1
                }
            }

            val remainder = n - firstIndex
            count += remainder

            if(count > n){
                break@loop
            }
        }

        if(count >= n){
            low = mid + 1
            result = mid
        } else {
            high = mid - 1
        }
    }

    bw.write(result.toString())
    bw.flush()
    bw.close()
    br.close()
}

결과

위 - 힙
아래 - 파라메트릭 서치