[TIL]LeetCode#42

minhyuk_ko·2022년 2월 5일
0

TIL

목록 보기
4/7

42. Trapping Rain Water

입력

[0,1,0,2,1,0,1,3,2,1,2,1]

출력

6

풀이

  • 첫번째 풀이(stack)
class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        vol = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                
                if not len(stack):
                    break
                
                distance = i - 1 - stack[-1]
                hei = min(height[i], height[stack[-1]]) - height[top]
                
                vol += distance * hei
            stack.append(i)
        return vol
  • 두번째 풀이(two pointer)
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        left, right = 0, len(height)-1
        left_max, right_max = height[left], height[right]
        vol =0
        
        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            
            if left_max <= right_max:
                vol += left_max - height[left]
                left += 1
            else:
                vol += right_max - height[right]
                right -= 1
                
        return vol

로직

투포인터: 왼쪽 끝과 오른쪽 끝에서 비교하면서 이전의 값이 현재 값보다 크면 이전 값에서 빼서 부피를 더한다.

스택: 변곡점(인덱스를 중심으로 기울기의 변화가 있는 곳)을 잡아 거리(현재 변곡점에서 이전 변곡점까지의 거리) * 높이(현재 변곡점과 이전 변곡점의 높이를 비교하여 낮은 요소)로 부피를 계산

느낀점

난이도가 어려운 문제였고 이에 대한 풀이도 그만큼 다양하게 접근할 수 있었다. 비록 책을 보면서 풀었지만 스택 방식이라는 처음보는 풀이를 해석하며 공부하였고 투포인터 풀이에 대한 생각을 깊게 할 수 있었다. 많이 풀어봐야 어떻게 풀지 감이 오겠지만 아직까진 난이도 높은 문제 풀이는 책에 의존해가면서 풀 수 밖에 없는 것 같다. ㅠㅠ

profile
BE Developer

0개의 댓글