[강남역 폭우] 풀이

문제

강남역에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다. 그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다.

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

#예시1. trapping_rain([3, 0, 0, 2, 0, 4]) -> 10

#예시2. trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) -> 6

내 풀이

1. 최대 층수를 구한다.
2. 최대 층수만큼 반복문을 돌린다.
3. 층별로 칸수만큼 반복문을 순차대로 돌려서 해당 칸수가 현재 층수(0층부터 시작)보다 크다면 해당 칸수를 시작인덱스로 설정한다.
4. 층별로 칸수만큼 반복문을 거꾸로 돌려서 해당 칸수가 현재 층수(0층부터 시작)보다 크다면 해당 칸수를 끝인덱스로 설정한다.
5. 층별로 지정한 시작 인덱스부터 끝 인덱스까지 반복문을 돌려서 특정 칸이 현재 층수(0층부터 시작)보다 작다면 count에 더해준다.

def trapping_rain(buildings):
    max_num = max(buildings)
    count = 0
   
    for i in range(max_num):
        start_index = None
        end_index = None
        for j in range(len(buildings)):
            if buildings[j] > i:
                start_index = j
                break
        for z in reversed(range(len(buildings))):
            if buildings[z] > i:
                end_index = z   
                break
        for x in range(start_index,end_index+1):
            if buildings[x] < i+1:
                count += 1
               
    return count 

모범답안

아래 방식을 따르면, 각 인덱스에 담기는 빗물의 양을 계산할 수 있습니다.

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