2021-11-20 강남역 폭우2

 

이 문제는 예전에 최대 건물 높이 중에서 최소값이 빗물이 담길 수 있는  최대 값이라고 했었다.

하지만 그렇게 하면 O(n^2)의 시간복잡도를 가지는데...

 

이를 해결하려면 최대 건물 높이를 미리 알아놓으면 좋을 것 같다.

 

def trapping_rain(buildings):
    container = 0
    left = []
    right = []
    
    for i in range(len(buildings)):
        left.append(max(buildings[:i+1]))
        right.append(max(buildings[i:]))
        
    for i in range(len(buildings)):
        container += (min(left[i], right[i]) - buildings[i])
    return container

2021-11-20