44. Trapping Rain Water

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

내 풀이

//986ms 48.6MB
fun trap(walls:IntArray):Int {
    var result = 0

    for (i in 1..<walls.size - 1) {
        var left = 0
        var right = 0

        for (j in i downTo 0) {
            left = max(left, walls[j])
        }
        for (j in i until walls.size) {
            right = max(right, walls[j])
        }
        result += min(left, right) - walls[i]
    }
    return result
}

2중 for문을 활용하여 O(n^2) 시간복잡도가 나왔다..

내 아이디어는 모든 칸을 순회하면서 min(왼쪽에서 가장 높은 벽과 오른쪽에서 가장 높은 벽) - 현재 벽의 높이를 계산하는 것이다.

투포인터 알고리즘

투포인터 알고리즘: 리스트에 순차적으로 접근해야 할때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘.

//199ms 39.8MB
fun trap(walls: IntArray):Int {
    var volume = 0
    var left = 0
    var right = walls.size - 1

    var left_max = 0
    var right_max = 0

    while (left < right) {
        left_max = max(left_max, walls[left])
        right_max = max(right_max, walls[right])

        if (left_max <= right_max) {
            volume += left_max - walls[left]
            left++
        } else {
            volume += right_max - walls[right]
            right--
        }
    }
    return volume
}

아이디어는 양쪽에서 출발하여서 가장 높은 쪽으로 움직이는 방법이다.

단일 while문을 사용해서 O(n)시간복잡도이다.

스택

//197ms 41.99MB
fun trap(walls: IntArray): Int {
    var stack = Stack<Int>()
    var volume = 0

    for (i in walls.indices) {
        while(!stack.isEmpty() && (walls[i]>walls[stack.peek()])) {
            var top = stack.pop()

            if (stack.isEmpty()) {
                break
            }

            val distance = i - stack.peek() - 1
            val waters = min(walls[i], walls[stack.peek()]) - walls[top]

            volume += distance * waters
        }
        stack.push(i)
    }
    return volume
}

아이디어는 스택에 쌓아가면서 현재 높이가 이전 높이 보다 높은 턱을 만날때를 기준으로 격차만큼 volue을 채우는 방법. for 안에 while이 들어있어서 O(n^2)처럼 보이지만 while문조건은 n에 관계가 있지 않고 stack.peek(), stack.pop()은 O(1)의 시간복잡도이므로 O(n)의 시간복잡도를 갖게 된다