Steve Choi

비전공자 출신 개발자 블로그.

Day016 - 42. Trapping Rain Water

업데이트:

42. Trapping Rain WaterPermalink

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

img

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105


내 풀이Permalink

class Solution:
    def water_cal(self, height):
        left_h = height[0]
        water_gain = False
        water = 0

        for i in range(1, len(height)):
            if water_gain == False: # 물이 안 고이고 있을 때.
                if left_h <= height[i]: # 다음 땅이 왼쪽 기준점보다 높이가 같거나 더 높을 때(물 안고임)
                    left_h = height[i] # 왼쪽 기준점을 height[i]로 갱신
                else: # 다음 땅이 왼쪽 기준점보다 높이가 낮을 때 (물 고임)
                    water_gain = True # 물 고이는 상태로 전환
                    water += left_h - height[i] # 왼쪽 기준점을 기준으로 고이는 물의 양 계산
                
            else: # 물이 고이고 있을 때.
                if left_h <= height[i]: # 다음 땅이 왼쪽 기준점보다 높이가 같거나 더 높을 때(물이 더이상 고일 수 없음)
                    water_gain = False # 물이 고이지 않는 상태로 전환
                    left_h = height[i] # 왼쪽 기준점을 height[i]로 갱신
                else: # 다음 땅이 왼쪽 기준점보다 높이가 낮을 때 (물이 계속 고임)
                    water += left_h - height[i] # 왼쪽 기준점을 기준으로 고이는 물의 양 계산
        return water # 고여있는 전체 물의 양을 return


    def trap(self, height: List[int]) -> int:
        max_h = max(height)
        max_idx = height.index(max_h)

        height_1, height_2 = height[:max_idx+1], height[max_idx:]
        height_2.reverse()

        answer = self.water_cal(height_1) + self.water_cal(height_2)
        return answer

이번 문제는 난이도가 hard였는데, 생각보다 쉽게 한 번에 풀었다.

# Time Complexity : O(N)


댓글남기기

참고