[Algorithm] Python 강남역 폭우

* 본 문제는 코드잇에서 제공하는 문제이므로 자세한 문제 내용은 적지 않겠습니다.

 

[문제]

[3, 0, 0, 2, 0, 4]

 

[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

[해설]

위와같이 빨간색으로 표시된 곳이 빌딩이고, 하늘색으로 채워지는 곳이 빗물이 담길 수 있는 공간이다.

빗물이 담길 수 있는 하늘색 공간의 총 합을 구하는 것이 문제이다.

 

처음에 고려했던 풀이는 효율성이 떨어지는 것 같아 힌트를 참고하여 풀었다.

1. 양 쪽 끝 인덱스에는 물이 찰 수 없으므로 제외하고 1번 index부터 end - 1 인덱스까지 고려한다.

2. 현 인덱스를 기준으로 왼쪽의 가장 큰 값과 오른쪽의 가장 큰 값을 저장한다.

3. 왼쪽 max값과 오른쪽 max값을 비교하여 더 작은 값을 빗물이 고일 수 있는 최대높이로 저장한다.

4. 빗물이 고일 수 있는 최대 높이가 현재 빌딩높이보다 낮으면 빗물이 쌓일 수 없다.

 

[코드]

def trapping_rain(buildings):
    total_val = 0
    for i in range (1, len(buildings) - 1):  # 양쪽끝에 인덱스에는 물이찰 수 없음
        max_left = max(buildings[:i])        # 현 인덱스부터 왼쪽의 가장 큰 값
        max_right = max(buildings[i:])       # 현 인덱스부터 오른쪽의 가장 큰 값
        limit_val = min(max_left, max_right) # 빗물이 고일 수 있는 최대 높이
        total_val += max(0, limit_val - buildings[i]) 
        # 빗물이 고일 수 없는 경우에는 빗물이 고일 수 있는 최대 높이보다 현 인덱스가 크거나 같은 경우
        
    return total_val


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