[백준 10868 - Kotlin] 최솟값

문제링크

• 세그먼트 트리 강의 영상

import java.io.BufferedReader
import java.io.BufferedWriter
import kotlin.math.min
import kotlin.math.pow

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var input: MutableList<Int>
private lateinit var segTree: Array<Int>

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    // 1. get n, m
    val (n, m) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }

    // 2. get input
    input = mutableListOf()
    for (i in 0 until n) {
        input.add(bufferedReader.readLine().toInt())
    }

    // 3. construct segTree
    val segTreeSize = getSegTreeSize(n)
    segTree = Array(2 * segTreeSize - 1) { Int.MAX_VALUE }
    constructSegTree(0, n - 1, 0)

    // 4. get (a, b)
    for (i in 0 until m) {
        val (a, b) = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }
        val answer = rangeMinQuery(a - 1, b - 1, 0, n - 1, 0)
        bufferedWriter.write("$answer\n")
    }
    bufferedReader.close()
    bufferedWriter.close()
}

fun getSegTreeSize(n: Int): Int {
    var exponent = 1.0
    while (n > 2.0.pow(exponent)) {
        exponent++
    }
    return 2.0.pow(exponent).toInt()
}

fun constructSegTree(low: Int, high: Int, pos: Int) {
    if (low == high) {
        segTree[pos] = input[low]
        return
    }

    val mid = (low + high) / 2
    constructSegTree(low, mid, 2 * pos + 1)
    constructSegTree(mid + 1, high, 2 * pos + 2)
    segTree[pos] = min(segTree[2 * pos + 1], segTree[2 * pos + 2])
}

fun rangeMinQuery(qLow: Int, qHigh: Int, low: Int, high: Int, pos: Int): Int {
    if (qLow <= low && qHigh >= high) return segTree[pos]
    if (qLow > high || qHigh < low) return Int.MAX_VALUE

    val mid = (low + high) / 2
    return min(
        rangeMinQuery(qLow, qHigh, low, mid, 2 * pos + 1),
        rangeMinQuery(qLow, qHigh, mid + 1, high, 2 * pos + 2)
    )
}