[파이썬 알고리즘 인터뷰] 빗물 트래핑

Trapping Rain Water - LeetCode

나의풀이

def trap(self, height: List[int]) -> int:
        left,right=0,len(height)-1
        left_max=height[left]
        right_max=height[right]
        trapped=0
        while left!=right:
            if left_max<=right_max:
                left+=1
                left_max=max(height[left],left_max)
                trapped+=(left_max-height[left])
                
            elif left_max>right_max:
                right-=1
                right_max=max(height[right],right_max)
                trapped+=(right_max-height[right])
            
        return trapped

투포인터를 이용한 풀이로 왼쪽 포인터의 최댓값과 오른쪽 포인터의 최댓값을 비교하여 포인터를 이동하고 두 포인터의 최댓값 중 작은 값과 현재 포인터의 값 차이를 이용하여 갇힌 물의 양을 구했다.

투 포인터를 최대로 이동

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,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

투 포인터를 이용한 나의 방법과 동일한 아이디어로 푼 풀이이다. 코드가 조금 더 깔끔하게 작성되어 있어 참고하면 좋을 것 같다.

스택 쌓기

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

스택에 계속 쌓아가다가 변고점을 만나면 스택에서 하나씩 꺼내며 차이만큼 물 높이를 채워나가는 알고리즘인데, 솔직히 아직 잘 이해안된다.... 스택을 이용하여 이렇게 풀었다는 것 자체가 신기하다...ㅎㅎ