Leetcode 42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water

 

제가 생각한 아이디어는 다음과 같습니다.

 

왼쪽에서부터 오른쪽으로, 오른쪽에서 왼쪽으로 총 2번 탐색을 합니다. 이때, 처음과 끝은 채울 수 없으므로 첫 높이로만 지정하고 물을 채우지는 않습니다.

왼쪽에서 오른쪽으로 탐색할 때, 방문한 벽이 탐색하며 방문한 가장 큰 벽보다 작을 경우, 가장 큰 벽 높이 - 현재 벽 높이만큼 물을 채울 수 있다고 기록합니다.

방문한 벽이 이전 가장 큰 벽보다 크거나 같은 경우에는 가장 큰 벽의 높이만 갱신하고 넘어갑니다.

 

 

다시 오른쪽에서 왼쪽으로 탐색할 때, 방문한 벽이 오른쪽에서 왼쪽으로 탐색하며 방문한 가장 큰 벽보다 작을 경우, 가장 큰 벽 높이 - 현재 벽 높이 값과 왼쪽에서 오른쪽으로 탐색할 때 기록했던 값 중 더 작은 값을 채울 수 있다고 기록합니다.

방문한 벽이 이전 가장 큰 벽보다 크거나 같은 경우에는 가장 큰벽의 높이를 갱신하고, 채울 수 있는 물의 높이를 0으로 갱신합니다.

 

그러면 정답이 됩니다!

 

class Solution {
    fun trap(height: IntArray): Int {
        var leftMaxHeight = height.first()
        val answer = IntArray(height.size)

        for (i in 1 until height.size-1) {
            if (height[i] > leftMaxHeight) {
                leftMaxHeight = height[i]
                continue
            } else if (height[i] == leftMaxHeight) {
                continue
            }
            answer[i] = leftMaxHeight - height[i]
        }
        var rightMaxHeight = height.last()

        for(i in height.size - 2 downTo 1) {
            if (height[i] > rightMaxHeight) {
                answer[i] = 0
                rightMaxHeight = height[i]
                continue
            } else if (height[i] == rightMaxHeight) {
                answer[i] = 0
                continue
            }
            answer[i] = min(answer[i], rightMaxHeight - height[i])
        }

        return answer.sum()
    }
}