문제 이동
난이도 : ⭐️

투 포인터 풀이

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 = max(height[left], left_max)
            right_max = max(height[right], right_max)
            
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
                
            elif left_max > right_max :
                volume += right_max - height[right]
                right -= 1
                
        return volume

왼쪽, 오른쪽 투 포인터를 활용하여 가장 긴 높이에 포인터가 도달하면 끝나도록 함.

스택 풀이

아직 이해 못해서 다음에 공부하고 업로드할 예정

+)

• 어렵다^^
  시간복잡도 이런 것보다 그냥 아예 이걸 어떻게 구해야 할지 생각하기도 힘들었다.

• 투 포인터를 이용하고 이동 종료 지점이 가장 긴 높이에 도달하는 것으로 지정하기 위해, left_max와 right_max의 길이를 이용해야 한다.
  어디부터 더해지든 간에 가장 긴 높이에 도달하면 아직 도달하지 못한 쪽에서 계속 계산해야 한다.
  양쪽 최대 길이 중 짧은 쪽에 대해 연산을 진행하면 양쪽 포인터가 최대 길이에서 만나게 되기 때문에 이를 기준으로 쭉 volume에 값을 더해주면 된다.

• 다시 풀기^^!

• 스택 풀이 이해하기!