Problem

solution

---

투포인터를 이용한 풀이

class Solution:
    def trap(self, height: List[int]) -> int:
        # height가 없다면 빠르게 예외처리
        if not height:
            return 0
        
        # 투포인터 생성
        left, right = 0, len(height) - 1
        volume = 0
        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
        
    

Stack을 이용한 풀이

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]]:
                # 스택에서 꺼낸다
                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

• Stack을 활용하여 문제를 푸는 방식인데, 현재높이가 이전높이보다 클때 stack에서 꺼내가면서 물높이를 계산하는 방법이다.

• 이문제에 대해서 바로 stack으로 풀어야지라는 생각은 들기 어려운 것같다. 그래서 이문제를 stack으로 푸는 방식을 이해하고 stack을 이용하는 방법에 익숙해져 나가야될 것 같다.

• Stack이란? 나중에 집어넣은 데이터가 먼저 나오는 구조 / LIFO (Last In First Out)