문제링크

풀이1 (Binary Search)

• height를 1부터 h까지 순회하여 height 보다 크거나 같은 석순(또는 종유석) 중 가장 작은 index를 반환합니다.
• 전체 석순(또는 종유석) 개수에서 해당 index를 뺀 값이 부딪히는 석순(또는 종유석)의 개수가 됩니다.

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

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter

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

    val (n, h) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }

    val downs = mutableListOf<Int>()
    val ups = mutableListOf<Int>()

    repeat(n) {
        val stone = bufferedReader.readLine().toInt()
        if (it and 1 == 0) downs.add(stone)
        else ups.add(stone)
    }

    downs.sort()
    ups.sort()

    var minCrashCount = Int.MAX_VALUE
    var minCrashSectionCount = 0

    for (height in 1..h) {
        val crashCount1 = ups.size - getFirstCrashIndex(ups, height, 0, ups.size - 1)
        val crashCount2 = downs.size - getFirstCrashIndex(downs, h + 1 - height, 0, downs.size - 1)
        if (crashCount1 + crashCount2 == minCrashCount) minCrashSectionCount++
        if (crashCount1 + crashCount2 < minCrashCount) {
            minCrashCount = crashCount1 + crashCount2
            minCrashSectionCount = 1
        }
    }
    bufferedWriter.write("$minCrashCount $minCrashSectionCount")

    bufferedReader.close()
    bufferedWriter.close()
}

fun getFirstCrashIndex(stones: MutableList<Int>, height: Int, _start: Int, _end: Int): Int {
    var start = _start
    var end = _end

    var firstCrashIndex = Int.MAX_VALUE
    while (start <= end) {
        val mid = (start + end) / 2
        if (stones[mid] < height) start = mid + 1
        else {
            firstCrashIndex = min(firstCrashIndex, mid)
            end = mid - 1
        }
    }

    if (firstCrashIndex == Int.MAX_VALUE) return stones.size
    return firstCrashIndex
}

풀이2 (Cumulative Sum)

• 석순(또는 종유석)의 누적합을 계산합니다.
• 높이를 1부터 h까지 순회합니다.
• 석순의 경우 가장 높은 높이의 누적합에서 현재 높이보다 1 낮은 높이에서의 누적합을 빼면 부딪히는 석순의 개수를 구할 수 있습니다.

import java.io.BufferedReader
import java.io.BufferedWriter

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter

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

    val (n, h) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }

    val downs = Array(h + 1) { 0 }
    val ups = Array(h + 1) { 0 }

    repeat(n / 2) {
        val down = bufferedReader.readLine().toInt()
        downs[down]++
        val up = bufferedReader.readLine().toInt()
        ups[up]++
    }

    for (i in 1..h) {
        downs[i] += downs[i - 1]
        ups[i] += ups[i - 1]
    }
    
    var minCrashCount = Int.MAX_VALUE
    var minCrashSectionCount = 0
    for (i in 1..h) {
        val crashCount1 = downs[h] - downs[i - 1]
        val crashCount2 = ups[h] - ups[h - i]

        if (crashCount1 + crashCount2 == minCrashCount) minCrashSectionCount++
        if (crashCount1 + crashCount2 < minCrashCount) {
            minCrashCount = crashCount1 + crashCount2
            minCrashSectionCount = 1
        }
    }

    bufferedWriter.write("$minCrashCount $minCrashSectionCount")

    bufferedReader.close()
    bufferedWriter.close()
}

주석 없는 코드를 만들기 위해 노력하는 개발자입니다.

혹시라도 의도가 분명하지 않아보이는 (이해가 되지 않는) 코드가 있으시다면 편하게 답변 달아주시면 정말 감사하겠습니다.