1. 문제

문제링크 : https://leetcode.com/problems/trapping-rain-water/

2. 풀이

2.1. 투 포인터

class Solution:
    def trap(self, height: List[int]) -> int:
        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]

        # left와 right이 만나기 전까지 반복
        while left < right:
            left_max, right_max = max(height[left], left_max),
            					  max(height[right], right_max)

            # 가장 높은 height을 향해서 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1

        return volume

height의 양쪽에서 움직이기 시작하는 투 포인터 left와 right를 활용한 방법이다. while문에서 반복마다 투 포인터의 현재 높이와 이전 높이를 비교하여 최대 높이를 left_max, right_max에 저장한다. 저장 후엔 left_max와 right_max를 비교하여 작거나 같은 쪽의 물 양을 계산하고 포인터를 이동시킨다. 왼쪽과 오른쪽의 최대 높이를 비교하며 포인터를 이동시키는 이유는 map에서 가장 높은 곳을 left_max 혹은 right_max로 설정하고 넘어가면 이후에 모든 곳을 물이 고인 것으로 계산하기 때문이다. 투 포인터가 만나기 전까지 한번 씩만 이동하므로 height의 원소 개수만큼만 움직인다. 따라서 $O(n)$의 시간 복잡도를 갖는다.

2.2. 스택

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        volume = 0

        for i in range(len(height)):
            while stack and height[stack[-1]] < height[i]:
                top = stack.pop()

                # stack이 비어있는 경우
                if len(stack) < 1:
                    break
                
                # stack[-1]에 해당하는 height와 i번째 height 사이 물의 너비, 높이
                water_w = i - stack[-1] - 1
                water_h = min(height[i], height[stack[-1]]) - height[top]

                volume += water_w*water_h

            stack.append(i)
        
        return volume

stack에 매 반복마다 height원소의 index를 push한다. while문은 stack의 top에 해당하는 원소보다 현재 height의 원소가 큰 경우, 즉 현재 높이가 이전보다 높은 경우에 실행된다. 실행되면 stack에서 pop한 값을 top에 저장한다. pop 이후에 stack이 비었으면 반복문을 탈출하는데, stack에 남아있는 값으로 물의 양을 계산할 것이므로 반복문을 탈출한다. 만약 stack이 비지 않았다면 현재 height의 원소와 stack[-1]에 해당하는 원소 사이의 물 양을 계산한다. while문이므로 stack에 여전히 현재 height원소보다 작은 원소를 가리키는 index가 있다면 반복한다. for문은 height 원소 개수만큼 반복하고 while문은 실행되는 총 횟수가 height 원소 개수를 넘을 수 없기 때문에 전체 시간 복잡도는 $O(n)$이 된다. 2.1. 투 포인터 풀이와 비교했을 때 실행시간에서 거의 차이가 없다.