런던 비, 건물 사이에 담기는 빗물 총량

런던에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다. 그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain()을 작성해 보려고 합니다. 함수 trapping_rain()은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다. 예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 33의 건물이, 3번 인덱스에 높이 22의 건물이, 5번 인덱스에 높이 44의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 없습니다. 그러면 아래의 사진에 따라 총 1010 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain() 함수는 10을 리턴하는 거죠.

 

 

 

===============Answer==============

문제를 해결하기 위해 빗물이 담길 수 있는 공간을 찾아야 합니다. 이를 위해 각 건물의 좌우로 가장 높은 건물을 찾아 그 사이의 공간을 계산하면 됩니다.

```python
def trapping_rain(buildings):
    n = len(buildings)
    if n <= 2:
        return 0
    
    left_max = [0] * n
    right_max = [0] * n
    
    left_max[0] = buildings[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], buildings[i])
    
    right_max[n-1] = buildings[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], buildings[i])
    
    water_trapped = 0
    for i in range(n):
        water_trapped += max(0, min(left_max[i], right_max[i]) - buildings[i])
    
    return water_trapped

buildings = [3, 0, 0, 2, 0, 4]
print(trapping_rain(buildings))  # Output: 10
```

위 코드에서는 먼저 각 건물의 왼쪽에서 가장 높은 건물과 오른쪽에서 가장 높은 건물을 구합니다. 그런 다음 각 위치에서 최소값을 구하여 현재 위치에서 담길 수 있는 빗물의 양을 계산합니다. 마지막으로 모든 위치에서 담길 수 있는 빗물의 양을 합하여 총 빗물의 양을 구합니다.