훌륭하게 자신만의 해설을 해주신 분들도 많았는데요.

저는 제 것이 아니라 그런지 제가 해결하지 않고 해설을 보려니 찝찝하더라구요..

그래서 코드를 짜봤습니다.

def trapping_rain(buildings):

    trapped_rain = 0 #갇힌 물
    current_tallest = 0 #현재 최고 높이 빌딩
    total_tallest = max(buildings) #빌딩 전체 중, 최고 높이

    for index in range(0, len(buildings)-1):
        # 첫 인덱스와 마지막 인덱스는 물이 찰 수 없다.
        # 첫 인덱스는 current_tallest를 지정해주고, 마지막 인덱스는 제외 len(buildings) - 1

        if (buildings[index] >= current_tallest) and (buildings[index] != total_tallest):
            # 현재 빌딩 높이가 지금까지 가장 높은 빌딩과 유사하거나 크면서
            # 현재 빌딩이 최고 높이 빌딩이 아닌 경우
            current_tallest = buildings[index]
            # 지금까지 가장 높은 빌딩을 현재 빌딩으로 지정

        if buildings[index] < current_tallest:
            # 현재 빌딩 높이가 지금까지 가장 높은 빌딩보다 작으면 (물이 찰 수 있는 조건)
            # 위에서 가장 높은 빌딩이 아닌 경우에 current_tallest로 지정해주기 때문에
            # 물이 찰 수 있는 조건이 된다.
            trapped_rain += current_tallest - buildings[index]

        print(buildings[index], current_tallest, total_tallest, trapped_rain)

    return trapped_rain

그런데! 제 코드를 여러 Test를 거치면서, 가장 큰 빌딩과 똑같은 빌딩이 또 있는 경우잘못 계산되는 오류가 있더군요..

그래서, 중간에 최고 높이 빌딩과 동일한 빌딩이 여러 개 있더라도 계산되는 코드를 추가했습니다.

이렇게 되니까 복잡해보여서 좀 그렇네요 마음이..

def trapping_rain(buildings):

    trapped_rain = 0 #갇힌 물
    current_tallest = 0 #현재 최고 높이 빌딩
    total_tallest = max(buildings) #빌딩 전체 중, 최고 높이

    for index in range(0, len(buildings)-1):
        # 첫 인덱스와 마지막 인덱스는 물이 찰 수 없다.
        # 첫 인덱스는 current_tallest를 지정해주고, 마지막 인덱스는 제외 len(buildings) - 1

        if (buildings[index] >= current_tallest) and (buildings[index] != total_tallest):
            # 현재 빌딩 높이가 지금까지 가장 높은 빌딩과 유사하거나 크면서
            # 현재 빌딩이 최고 높이 빌딩이 아닌 경우
            current_tallest = buildings[index]
            # 지금까지 가장 높은 빌딩을 현재 빌딩으로 지정

        if buildings[index] < current_tallest:
            # 현재 빌딩 높이가 지금까지 가장 높은 빌딩보다 작으면 (물이 찰 수 있는 조건)
            # 위에서 가장 높은 빌딩이 아닌 경우에 current_tallest로 지정해주기 때문에
            # 물이 찰 수 있는 조건이 된다.
            trapped_rain += current_tallest - buildings[index]

        if (buildings[index] == total_tallest) and (index != len(buildings)-1):
            # 하지만 가장 높은 빌딩이 몇 개 있다면 위의 코드만으로는 잘못 계산된다.
            # 이 경우에는 그냥 trapped_rain은 다음 인덱스들 중에서 가장 큰 빌딩을 구하고,
            # 현재 빌딩의 높이 차이만큼 비 양을 계산해주고 break한다.
            next_highest = max(buildings[index+1:])
            for i in range(index+1, len(buildings)-1):
                trapped_rain += next_highest - buildings[i]

            return trapped_rain

    return trapped_rain

주석을 빼면 간결해 보일까요?..

def trapping_rain(buildings):

    trapped_rain = 0 
    current_tallest = 0
    total_tallest = max(buildings) 

    for index in range(0, len(buildings)-1):

        if (buildings[index] >= current_tallest) and (buildings[index] != total_tallest):
            current_tallest = buildings[index]

        if buildings[index] < current_tallest:
            trapped_rain += current_tallest - buildings[index]

        if (buildings[index] == total_tallest) and (index != len(buildings)-1):
            next_highest = max(buildings[index+1:])
            for i in range(index+1, len(buildings)-1):
                trapped_rain += next_highest - buildings[i]

            return trapped_rain

    return trapped_rain

아마 시간복잡도는, for문이 중첩되지만 리스트를 한 번씩만 탐색하기 때문에 O(n)으로 생각되는데.

아니라면 ..(댓글로 알려주세요..)