[Leetcode] Trapping Rain Water - Two pointer / stack

1. 문제

https://leetcode.com/problems/trapping-rain-water/description/

 

2. 풀이

일단 풀이는 <파이썬 알고리즘 테스트> 참고하면서 공부중입니당

 

우선 구체적 풀이 전 뭔가 인사이트를 생각해보자면

빗물이 받아지는 부분은 붙어있는 막대라면 높이 차이가 날때, 높이가 0이면 옆 막대 vs 이전 막대 높이에 영향을 받는다

 

1) 투포인터 (two-pointer)

자, 우선 좌 와 우에서 각각 시작한다고 생각해보자

1-1) 0과 length-1에서 시작, 이 두 인덱스가 만날때까지 진행한다

1-2) 둘의 최대높이가 각각 있다고 가정하면, 그게 더 작은걸 다음인덱스로 이동한다

==> 이 이유는 낮은 막대가 물의 양을 결정하기 때문임, 단순하게 생각하면 막대가 3개뿐이면 [1,0,2], 2를 옮겨서 높이가 1인 물 양을 구하는거보다 1을 옮겨서 생각하는게 더 맞다

1-3) 이동할때마다 좌우 각각 최대 높이를 갱신하는데, 이제 다음 인덱스 높이가 최대 높이보다 작게되면 물이 고일 수 있다. 그러면 이때 물 양을 더해주고 다음 인덱스로 보내준다.
(사실 총량 더해주는 과정은 계속하는데 높이가 같아서 0이 더해지는것)

1-4) 양쪽에서 만나면 끝

 

 

## code ##

def trap(self, height: List[int]) -> int:
        # two-pointer

        volume, left, right = 0, 0, len(height)-1
        max_left, max_right = height[left], height[right]
        
        while left < right:
            max_left, max_right = max(height[left], max_left), max(height[right], max_right)

            if max_left > max_right:
                volume += max_right - height[right]
                right -= 1
            else:
                volume += max_left - height[left]
                left += 1
        
        return volume

 

2) 스택 (stack)

처음부터 쌓아가는과정으로 생각해보자

이경우에 알아야할것은, 우리는 stack에 높이가 있는 막대들을 저장해간다는 점이다.

0인경우에 총량을 저장하고, 이전 막대들을 저장하고, 이후에 복기하면서 그 차이만큼 나중 0일때 사용하는거다.

2-1) 스택을 준비하고, 물 양을 계산안하는 경우에는 계속 현재 인덱스를 쌓아간다.

stack.append(i)

2-2) 이때, 최종 저장 막대길이 < 현재 막대길이면 이제 물계산이 가능할 상황일지 모른다.

 while stack and height[i] > height[stack[-1]]:

2-3) 근데 이경우는 막대가 3개이상있어야 가능하다, 그래서 우선 현재 인덱스, 최종저장인덱스 + 스택에 하나더이상 남아있는지 확인한다

==> 이때 이미 최종저장인덱스를 pop해서 빼버리는데, 여기서 어차피 3개이상 없으면 얘는 다신 볼필요가 없다 ,,

2-4) 3개이상이라면, 물양은 가로 * 세로인 네모로 찾아야하는데, [가로는 인덱스], [세로는 높이]다.
가로 = 현재 인덱스 - 최종 인덱스 이전 인덱스 - 1
세로 = 현재 높이 - 최종 저장 높이 vs 최종 저장 이전 높이 - 최종 저장 높이 >> 비교해서 min 사용

 

## code ##

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

        volume = 0
        stack = []

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

                width = i - stack[-1] -1
                hgt = min(height[i] - height[top], height[stack[-1]] - height[top])

                volume += width * hgt

            # water block is poped, only stacked block saved.
            stack.append(i)
        return volume