[알고리즘 일기] 10. 강남역 폭우

 

 

문제 10. (2021-05-10)

강남역 폭우

강남역에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다.

그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다.

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

 

trapping_rain([3, 0, 0, 2, 0, 4]) 리턴값 : 10

trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) 리턴값 : 6

 

❧ 테스트 셋

def trapping_rain(buildings):
    #Code

#Test
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

---

❧ 정답

Try 1

def trapping_rain(buildings):
    rain_amount = 0
    for i in range(0, len(buildings)):
        left_height = buildings[0]
        right_height = 0
        for left in range(i-1, 0, -1):
            if left_height < buildings[left]:
                left_height = buildings[left]
        for right in range(i+1, len(buildings)):
            if right_height < buildings[right]:
                right_height = buildings[right]
        if right_height < left_height:
            lower_height = right_height
        else:
            lower_height = left_height
        if buildings[i] < lower_height:
            rain_amount += (lower_height - buildings[i])
    return rain_amount

print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

 

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

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

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

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

---

Try 2

def trapping_rain(buildings):
    rain_amount = 0

    for i in range(1, len(buildings) - 1):
        left_height = max(buildings[:i])
        right_height = max(buildings[i:])
        lower_height = min(left_height, right_height)
        # 양쪽 건물 높이 중 더 낮은 건물의 높이
        rain_amount += max(0, lower_height - buildings[i])
        # 양쪽 건물의 높이보다 낮은 경우에만 더함

    return rain_amount

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]))

 

1️⃣ Brute Force 패러다임

2️⃣ max, min 내장 함수 이용

3️⃣ max(buildings[:i]) 또는 max(builidings[i:])의 시간 복잡도 : O(n),

      for문의 경우, n에 비례하므로 시간 복잡도 : O(n2)