<백준> 빗물(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%EB%B9%97%EB%AC%BC

[백준]

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

제출 결과

 

쉽게 생각하고 접근했다가 잘 안 풀렸던 문제다.

 

가장 처음에는 양쪽 기둥을 기준으로 삼아서 문제를 해결하려고 했다.

그래서 처음 블록 높이를 기준으로 삼고 이보다 크거나 같은 블록이 등장하면 반복문을 돌면서 양쪽 높이에서 작은 거만큼 채우고 기준을 현재 블록으로 변경하는 식으로 짰다.

이렇게 짜니까 큰 높이에서 작은 높이를 체크하지 못하는 경우가 발생했다.

그래서 반대로 다시 반복문을 돌리는 식으로 땜빵을 하려고 했지만 양쪽 끝이 같은 높이인 경우에 두배로 결과가 나오는 걸 보며 이 코드는 안 되겠다 싶어서 코드를 다 갈아엎었다.

이 때 제출을 한 번 했었는데 바로 틀렸다.

 

다른 방법으로는 반복적으로 층마다 채우는 것도 생각했었다.

하지만 이것도 중복되는 값 처리가 해결되지 않아서 코드를 작성하던 도중 지웠다.

 

마지막으로 한 방법은 양옆 블록 기준이 아니라 현재 칸을 기준으로 하는 방법이었다.

'현재 칸이 빗물을 고일 수 있는 칸인가?'를 체크하고 채울 수 있는만큼 채우는 흐름이다.

체크하는 방법은 현재칸의 좌측 블록들 높이에서 가장 큰 값, 우측 블록들 높이에서 가장 큰 값을 비교하여 작은 값을 가져오고 이를 현재 칸의 블록 높이와 비교하는 것이다.

현재 칸의 블록 높이보다 크면 빗물이 그 값까지 빗물이 고일 수 있고, 작으면 빗물이 고일 수 없는 칸임을 알 수 있다.

채우는 건 좌우측을 비교하여 가져온 작은 값에서 현재 칸의 블록 높이를 뺀 값만큼 채우면 된다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    var answer = 0
    var st = StringTokenizer(readln())
    val h = st.nextToken().toInt()
    val w = st.nextToken().toInt()
    val blocks = arrayListOf<Int>()

    st = StringTokenizer(readln(), " ")
    repeat(w) {
        blocks.add(st.nextToken().toInt())
    }

    for (i in 1 until blocks.lastIndex) {
        val min = minOf(blocks.slice(0 until i).maxOf { it }, blocks.slice(i + 1..blocks.lastIndex).maxOf { it })

        if (min > blocks[i]) answer += (min - blocks[i])
    }

    println(answer)
}