[Brute Force] 런던 폭우

코드잇 강의를 통해 알고리즘에 대해 공부하며 배운 내용들을 기록한 글입니다.

---

문제 설명

런던에 엄청난 폭우가 쏟아진다고 가정하자 ☔
정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도이다.

그렇게 되었을 때, 건물곽 건물 사이에 얼만큼의 빗물이 담길 수 있는지 알고 싶다!
그것을 계산해 주는 함수 trapping_rain을 작성해 보려 한다.

함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 준다.

예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 하자. 그러면 0번 인덱스에 높이 $3$의 건물이, 3번 인덱스에 높이 $2$의 건물이, 5번 인덱스에 높이 $4$의 건물이 있다는 뜻이다. 1번, 2번, 4번 인덱스에는 건물이 없다.

그러면 아래의 사진에 따라 $10$ 만큼의 빗물이 담길 수 있다.
따라서 trapping_rain함수는 10을 리턴하게 되는 것이다.

이번에는 파라미터 buildings로 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]가 들어왔다고 하자.
그러면 아래의 사진에 따라 총 $6$만큼의 빗물이 담길 수 있다. 따라서 trapping_rain함수는 6을 리턴하는 것이다.

이 정보를 기반으로, trapping_rain함수를 작성해 보자!

# 테스트 코드
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

10
6

---

나의 풀이

def trapping_rain(buildings):
    total_rain = 0

    for i in range(1, len(buildings) - 1):
        max_left = max(buildings[:i])
        max_right = max(buildings[i:])

        # 현재 인덱스에 빗물이 담길 수 있는 높이
        now_height = min(max_left, max_right)

        # 현재 인덱스에 담기는 빗물의 양을 계산
        # 만약 upper_bound가 현재 인덱스 건물보다 높지 않다면, 현재 인덱스에 담기는 빗물은 0
        total_rain += max(0, now_height - buildings[i])

    return total_rain

# 테스트 코드
print(trapping_rain([0, 3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

우선 빗물이 담기기 위해 충족되어야 할 조건을 생각해보았다!

일단 바로 알 수 있는 점은, 0번 인덱스와 마지막 인덱스에는 빗물이 담길 수 없다.
다시 한번 그림을 보자.

1번 인덱스에는 왼쪽에 더 높은 건물이 없기 때문에 빗물이 담기지 않는다.
반면에 2번 인덱스에는 양쪽에 모두 건물이 있기 때문에 빗물이 담기게 된다.

마찬가지로 4번 인덱스에는 물이 담겨 있다.
4번 인덱스에는 높이 $1$의 건물이 있는데, 양쪽에 모두 높이 $1$보다 높은 건물이 있기 때문이다,

즉, 더 큰 건물들 사이에 있으면 빗물이 담기게 된다.

빗물이 담기는 조건을 알았으니 이제 빗물의 양을 계산하는 방법을 알아보자.

다시 4번 인덱스를 살펴보자
4번 인덱스를 기준으로 왼쪽에서 가장 높은 건물은 3번 인덱스에 있고, 오른쪽에서 가장 높은 건물은 7번 인덱스에 있다.
3번 인덱스의 건물은 높이가 $2$이고, 7번 인덱스의 건물은 높이가 $3$이고, 4번 인덱스에 담긴 빗물의 양은 $1$이다.

물이 담기는 것은 4번 인덱스 건물의 높이인 $1$부터 시작해서, 3번 인덱스와 7번 인덱스의 건물 중 더 낮은 높이인 $2$까지이다. 그래서 $1$만큼의 빗물만 담기는 것이다!

그래서 빗물의 양을 계산하는 방법은 아래와 같다.

1.현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다.
2.현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다.
3.그 중 더 낮은 건물의 높이를 구한다.
4.그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다.

이제 코드로 구현하기 위해서 우선 0번 인덱스와 마지막 인덱스는 볼 필요가 없기 때문에

    for i in range(1, len(buildings) - 1):

반복문의 범위를 이렇게 지정해 주었다.

그리고 반복문을 돌면서 현재 인덱스를 기준으로 양쪽에 가장 높은 건물의 위치를 구해서 각각 max_left, max_right에 저장해 둔다.

        max_left = max(buildings[:i])
        max_right = max(buildings[i:])

위에서 정리한 방법을 토대로, 양쪽 건물 중 더 낮은 건물의 높이를 구해 now_height에 저장해주고, 거기에서 현재 건물의 높이를 빼서 빗물의 양을 계산해 주었다.

만약 now_height가 현재 인덱스의 건물보다 낮으면 담기는 빗물이 0이기 때문에,
max함수를 사용해서 해당 경우에는 0이 출력되도록 하였다.

그렇게 출력된 값을 total_height에 계속 업데이트 시켜주면 끝이다!