배열: 빗물 트래핑

빗물 트래핑

문제 설명

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

def solution(rains):
    if not rains:
        return 0
    vol = 0
    left, right = 0, len(rains) - 1
    left_max, right_max = rains[left], rains[right]

    while left < right:
        left_max, right_max = max(rains[left], left_max), max(rains[right], right_max)
        if left_max <= right_max:
            vol += left_max - rains[left]
            left += 1
        else:
            vol += right_max - rains[right]
            right -= 1

    return vol

문제 풀이

• 이 문제는 brute force로 풀게 되면 시간 초과로 틀리게 된다.
• 그래서 최대한 최적화에 신경을 써야하고, 여기서는 투 포인터 방식으로 해결하게 되었다.
  - 투포인터: 양 옆에 포인터를 두고 조건에 따라서 포인터를 옮기는 방식으로 해결하는 방식. O(n)으로 풀이 가능.
• 양 끝의 max값을 업데이트하면서 vol 값에 계속 변화를 준다.
• 높이가 최대로 가게 될 경우 해당 알고리즘은 끝나게 되고, 비의 양을 계산할 수 있게 된다.