[Leetcode] 42. Trapping Rain Water
'파이썬 알고리즘 인터뷰' 책으로 코딩테스트 공부하다가 풀이를 봐도 이해가 가지 안하는 부분이 있어 일단 기록해두고 나중에 다시 차근차근 이해하려고 남겨두기!
- Trapping Rain Water
높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.
1번째 방법. 투 포인터를 최대로 이동
이 방법 다른 블로그 글을 통해 이해가 되었다.
class Solution:
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
2번째 방법. 스택 쌓기
이 방법은 다른 블로그 글을 봐도 잘 이해가 되지 않는다...
class Solution:
def trap(self, height: List[int]) -> int:
stack = []
volume = 0 # 채워지는 물 눞이
for i in range(len(height)):
# 변곡점을 만나는 경우
while stack and height[i] > height[stack[-1]]: # stack[-1]: 스택에서 원소를 제거하지 않고 가져오기만 할 때 사용
# 스택에서 꺼낸다
top = stack.pop()
if not len(stack):
break
# 이전과의 차이만큼 물 높이 처리
distance = i - stack[-1] -1
waters = min(height[i], height[stack[-1]]) - height[top]
volume += distance * waters
stack.append(i)
return volume
Author And Source
이 문제에 관하여([Leetcode] 42. Trapping Rain Water), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tnqls1211v/Leetcode-42.-Trapping-Rain-Water저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)