리트코드 42. 빗물 트래핑(파이썬)

알고리즘/배열

by NayC 2021. 9. 16. 19:51

728x90

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

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

[접근 고민]
Q. 저 height가 의미하는게 뭐지?

-> 맨 앞에 부분도 세어주는거였다.

- 뭔가... 높이에 따라서, 파란색 물이 채워지는 공간을 어떻게든 계산해줘서 출력해주는 문제인데...
- 다행히 주어진 리스트는 '다' black 부분만 가리키는거고,

height = [0,1,0,2,1,0,1,3,2,1,2,1]
빗물이 있기 위한 조건은 2개다.
1) 앞 > 뒤
2) 그리고(!) 뒤에건 그 뒤에거보다 작아야 함

//

* 다른 접근
1) 정렬에서 가장 큰 수 (여기서는 3)를 찾은 다음에, 여기까지 접근은 아주 옳다. '투 포인터' 한 층 한층 바라봐줘볼까 -> 양 옆에서
- 예를 들어, 1층이면 -> 1층인데 1보다 작은 곳에는 물이 차있겠지. (2개)
- 2층이면 -> 2보다 작은 곳에 물이 있는데, 또 조건은 2-1인 곳은 그냥 세어줘도 되는데 그 이하는(0) 1층에서도 세어줬으니 하나 제해주기 (이거 코드 짜기가 초큼 어렵겠네)

+ 대신 조건이 있겠다. 2----2 이런식으로 같은 층으로 묶어서 봐줘야. '그 사이' 고여있는걸 세주는거니까

p.s '이건 도저히 모르겠다' 싶었는데 5분만 더 생각해보자... 하는 그 5분 사이에 다른 시각이 보였다. 👌.
p.s 어제 답 코드를 보는데도 뭐지? 싶어서 하루 건너 지금 다시 보는데 보인다... 😊✌️

[코드 짜기]

[올바른 코드를 확인해보자]

def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]

        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            # 더 높은 쪽을 향해 투 포인터 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return volume

* 아이디어 *

1) '최대 높이 막대'는 무한대여도 상관 없음
- 전체 부피에 영향 x
- just 오른쪽과 왼쪽을 가르는 장벽 역할

2) '최대 높이 막대'까지 /
각각 좌우 기둥 최대 높이 left_max, right_max가 현재 높이와의 차이만큼 물 높이 volume을 더해 나가는 것