[LeetCode] 42. Trapping Rain Water (Daily Question)

문제

---

 

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:

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

 

풀이

---

아이디어

처음에는 for문으로 앞에서부터 살펴보려 했으나 복잡해졌다.

 - 물이 차게 되려면 기둥과 기둥사이에 낮은 부분이 있어야 한다.

 - but, 앞의 기둥은 쉽게 찾을 수 있으나 뒤의 기둥은 찾는게 까다롭다.

 

따라서 구현을 멈추고 높이별로 차게 될 물의 양을 구하는 방식을 생각해냈다.

 

 

높이 1 살펴보기

 

 

양쪽 기둥 사이의 너비 = p2 - p1 = 11
양쪽 기둥 사이의 기둥 개수 = 9

물의 양 = 11 - 9 = 2

 

 

 

높이 2 살펴보기

 

양쪽 기둥 사이의 너비 = p2 - p1 = 8
양쪽 기둥 사이의 기둥 개수 4

물의 양 = 8 - 4 = 4

 

 

 

코드

# 높이마다 물이 얼마나 차게 되는지 확인

from collections import Counter
class Solution:
    def trap(self, height: List[int]) -> int:
        answer = 0
        height_c = Counter(height)

        # 현재 높이 이상의 기둥 개수
        ln = len(height)

        # 현재 높이 기준 앞 기둥
        p1 = 0
        # 현재 높이 기둥 뒷 기둥
        p2 = len(height)-1

        for n in range(1, max(height)+1):
            # 현재 높이 이하의 기둥 제거
            if n-1 in height_c: ln -= height_c[n-1]

            # 기둥 업데이트
            while height[p1] < n:
                p1 += 1

            while height[p2] < n:
                p2 -= 1

            # 기둥 사이의 너비 - 그 사이에 있는 기둥의 수 = 현재 높이에 차게 될 물의 양
            answer += p2 - p1 - ln + 1
        
        return answer

---

 

후기

---

난이도

처음에 방향을 잘못잡아 시간, 노력 낭비를 많이 했다.

 

적당한 아이디어를 떠올리기에는 쉽지 않았고, 아이디어를 떠올리고 나서 구현한 이후에도 시간초과때문에 최적화하는 과정이 필요했다.

 

예외는 딱히 없어서 다행이었다.