Leetcode 42. Trapping Rain Water - Python

from LeetCode 42

 

Leetcode 42 문제 보기

 

문제 이해하기

높이에 관한 정보가 주어질 때, 가둘 수 있는 빗물의 부피를 구하라.

예를 들어, height = [0,1,0,2,1,0,1,3,2,1,2,1] 일 때(위 그림 참조), 정답은 6이다.

 

아이디어 구상

가장 먼저 떠오른 생각은, 가장 높은 지점을 기준으로 좌우를 나누어 계산하면 될 것 같다라는 점이다.

 

다음처럼 생각해보자.

가장 높은 곳을 기준으로 좌측 영역을 우선 생각해보자.

첫 시작부터 포인터가 이동하면서 max값을 업데이트하며, max와 현재 지점의 높이의 차를 정답에 더해준다. 포인터는 전체에서 가장 높은 곳에 도달하면 멈추게 된다. 이렇게 되면 좌측 영역에서, 우측에는 분명한 '벽'(전체에서 가장 높은 지점)이 존재하므로 영역 내 높이 낮아지는 지점에는 물이 분명 담기게 될 것이라는 확신이 있게 된다.

가장 높은 곳을 기준 우측 영역 또한 마찬가지의 논리로 생각해볼 수 있다.

 

만약 가장 높은 지점이 한 곳이 아니라 중복되어 나타난다해도,

그들 중 한 곳을 기준으로 위와 같은 프로세스를 반복하면 정답이 도출됨을 상상해볼 수 있다.

 

그렇다면 코드로 구현해보자.

 

풀이

우선 부피 volume을 선언하고, 전체에서 가장 높은 지점의 인덱스 값을 구한다.

volume = 0
max_height_idx = height.index(max(height))

 

이후 max_height_idx를 기준으로 왼쪽 영역과 오른쪽 영역에 대해 구현해보자.

리스트의 첫번째 인덱스에서 시작하여 max_height_idx와 만날 때까지 포인터를 이동한다.

이때 영역 내 최대 높이를 업데이트하고, 이 높이보다 현재 위치에서의 높이가 작다면 물이 담길 수 있으므로 그 차이를 volume에 더해준다.

left, left_max = 0, height[0]
while left < max_height_idx:
    if height[left] >= left_max:
        left_max = max(left_max, height[left])
    else:
        volume += left_max - height[left]
    left += 1

 

동일한 논리로 max_height_idx 기준 우측 영역도 구현할 수 있다.

right, right_max = len(height) - 1, height[len(height) - 1]
while right > max_height_idx:
    if height[right] >= right_max:
        right_max = max(right_max, height[right])
    else:
        volume += right_max - height[right]
    right -= 1

 

전체 코드는 다음과 같다.

class Solution:
    def trap(self, height: List[int]) -> int:
        
        volume = 0
        max_height_idx = height.index(max(height))
        
        # left side of max_height
        left, left_max = 0, height[0]
        while left < max_height_idx:
            if height[left] >= left_max:
                left_max = max(left_max, height[left])
            else:
                volume += left_max - height[left]
            left += 1
        
        # right side of max_height
        right, right_max = len(height) - 1, height[len(height) - 1]
        while right > max_height_idx:
            if height[right] >= right_max:
                right_max = max(right_max, height[right])
            else:
                volume += right_max - height[right]
            right -= 1
        
        return volume

 

---

Leetcode 42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다