[알고리즘] 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

해설

힌트1

담기는 빗물의 총량을 구하기 위해서는, 각 인덱스에 담기는 빗물의 양을 계산해서 모두 더해줘야한다.

 

힌트2

특정 인덱스에 빗물이 담기기 위해서는 어떤 조건을 충족해야 할까?

 

힌트3

파라미터 buildings로 리스트  [0,1,0,2,1,0,1,3,2,1,2,1]를 받았다고 하자.

 

힌트4

일단 바로 알 수있는 점은, 0번 인덱스와 마지막 인덱스에는 빗물이 담길 수 없는 것이다.

그렇다면 그 외 나머지 인덱스에는 어떤 경우에 빗물이 담길 수 있을까?

 

힌트5

다시한번 그림을 들여다 보면

1번 인덱스에는 높이 1의 건물이 있다. 하지만 1번 인덱스의 왼쪽에는 더 높은 건물이 한개도 없기 때문에 빗물이 담기지 않고 모두 흘러 내려간다.

 

그에반해 2번 인덱스에는 빗물이 담겨있다. 2번 인덱스에는 건물이 없는데, 2번 인덱스의양쪽에는 모두 건물이 있기 때문이다.

 

마찬가지로 4번 인덱스에는 물이 담겨 있다. 4번 인덱스에는 높이 1의 건물이 있는데, 왼쪽으로는 높이 2의 건물이 있고 오늘쪽으로는 높이 3의 건물이 있기 때문이다.

 

즉 더 큰건물들 사이에 끼어 있으면 빗물이 담기는 것이다.

 

힌트6

'4번 인덱스를 살펴보자.

 

4번 인덱스의 왼쪽으로 가장 높은 건물은 3번 인덱스에 있고, 4번 인덱스의 오른쪽으로 가장 높은 건물은 7번 인덱스에 있다. 3번 인덱스의 건물은 높이가2이고 7번 인덱스의 건물은 높이가 3인데요. 4번 인덱스에 담긴 빗물의 양은 1이다.

 

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

 

즉  풀이방법을 정리해보면

 

1. 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다.

2. 현재 인덱스의 오른쪽에서 가장높은 건물의 높이를 구한다.

3. 그중 더 낮은 건물의 높이를 구한다.

4.그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다.

 

 

 

답안

def trapping_rain(buildings):
    # 총 담기는 빗물의 양을 변수에 저장
    total_height = 0

    # 리스트의 각 인덱스을 돌면서 해당 칸에 담기는 빗물의 양을 구한다
    # 0번 인덱스와 마지막 인덱스는 볼 필요 없다
    for i in range(1, len(buildings) - 1):
        # 현재 인덱스를 기준으로 양쪽에 가장 높은 건물의 위치를 구한다
        max_left = max(buildings[:i])
        max_right = max(buildings[i:])

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

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

    return total_height

# 테스트 코드
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]))