[LeetCode] 42. Trapping Rain Water - Python

🤔 문제

---

Trapping Rain Water - LeetCode

 

😀 풀이

---

해당 문제는 벽 높이 정보를 가지고 있는 배열을 이용하여 비가 온 뒤 벽 사이에 고인 빗물 양을 계산하는 문제입니다.

 

각 위치마다 고일 빗물의 양을 계산하는 과정을 통해 문제 풀이를 진행했는데 이 때 고려해야 할 것은 다음과 같습니다.

 

# 현재 위치 기준으로..

1. 좌측에 있는 벽들 중 최대 높이
2. 우측에 있는 벽들 중 최대 높이

위 두 가지를 안다면 두 가지 중 최소 값에서 현재 높이를 뺀 양이 고이는 빗물 양이 됩니다. 

 

즉, 현재 위치 높이가 2이고 좌측이 4, 우측이 5라는 높이를 가지고 있다면 현재 위치에는 (4 - 2) 만큼의 빗물이 고이기 때문이죠.

 

이때 주의할 점은 현재 높이가 좌측 혹은 우측보다 높다면 빗물이 고이지 않습니다.

 

위와 같은 알고리즘을 작성하다가 좀 더 효율적인 방법을 찾게되었는데 모든 벽 중 가장 높은 벽 하나를 기준으로 잡는 풀이 방식을 생각했습니다.

 

가장 높은 벽을 기준으로 좌측을 훑어보고 그 뒤 우측도 훑어보는 방식을 사용한다면 현재 위치 기준으로 매번 좌, 우측의 벽 최대 높이를 구하지 않아도 되기 때문에 조금 더 빠르게 계산할 수 있습니다.

 

아래 코드는 전체 풀이 코드의 일부분입니다.

max_height = max(height)
max_place = height.index(max_height)

left_max = height[0]

# left 돌기
for i in range(max_place):
    left_max = max(left_max, height[i])
    answer += left_max - height[i]

 

코드를 살펴보게 되면 가장 높은 벽을 기준으로 좌측을 훑어보는 과정인데 좌측 벽의 최대 높이를 현재 위치를 살펴가며 갱신해나가는 과정도 확인할 수 있습니다. for문 안의 left_max에서 갱신하고 있죠!

 

 또한 left_max - height[i], 즉 좌측 벽의 최대 높이와 현재 높이의 차를 통해 현재 위치에 고인 빗물 양을 구하고 있습니다. 이 과정을 통해 for문이 끝난다면 가장 높은 벽을 기준 좌측에 고인 빗물 양이 전부 구해집니다.

 

이제 똑같은 방식으로 우측을 살펴본다면 답을 구할 수 있습니다.

 

---

💻 풀이 코드는 아래와 같습니다.

 

class Solution:
    def trap(self, height: List[int]) -> int:
        answer = 0
        max_height = max(height)
        max_place = height.index(max_height)
        
        left_max = height[0]
        right_max = height[-1]
        
        # left 돌기
        for i in range(max_place):
            left_max = max(left_max, height[i])
            answer += left_max - height[i]
        
        # right 돌기
        for i in reversed(range(max_place, len(height))):
            right_max = max(right_max, height[i])      
            answer += right_max - height[i]      
        
        return answer