빗물 트래핑

Q : 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

ex ) [1,0,2,0,1,1,3] -> 5 (그림참조)

풀이 1 : 투 포인터를 최대로 이동

def trap(height):
   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

• 투 포인터를 양쪽 끝에서 출발시키는데, 각각 포인터에서의 최대값을 비교해보고 오른쪽이 더 높으면 왼쪽 포인터를 오른쪽으로 한칸이동 후 비교하고 왼쪽 포인터에서의 최대값이 높으면 오른쪽 포인터를 왼쪽으로 이동하는 방식입니다.
• 포인터를 옆으로 한칸 이동할 때마다 그 당시의 최대값과 현재 포인터에서의 높이값을 뺀 값을 volume 변수 값에 추가시켜줍니다.
• 예제의 경우에는 오른쪽 포인터의 최대값이 3으로 전체 최대값과 같기 때문에 왼쪽 포인터만 오른쪽으로 이동을 하며 쌓일 수 있는 빗물을 volume값에 추가하면서 이동합니다.
• 포인터가 만날 경우 left와 right의 값이 같아지므로 반복문을 빠져나오고 그때의 volume값을 return합니다.

풀이 2: 스택 쌓기

def trap(height):
    stack = []
    volume = 0
    
    for i in range(len(height)):
        
        # 현재 높이가 이전 높이보다 높을 때 수행되는 반복문
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            
            # len(stack)이 0일 경우 break
            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 리스트에 인덱스를 하나씩 추가해주는 for문이 기본적인 첫번째 반복문입니다.
• stack이 빈 리스트가 아니고 인덱스가 오른쪽으로 갈 때 높이가 올라가는 경우 while문이 수행됩니다.
• while문이 수행될 경우 stack의 마지막 값이 빠지면서 top에 저장됩니다.
• 그리고 top으로 값을 뺐을 때, stack이 빈 리스트가 아니라면 volume에 값을 더하는 과정이 진행됩니다.
• 거리는 현재의 인덱스와 stack의 마지막 값의 리스트에서 1을 뺀값으로 지정되고, 높이는 그 둘의 높이의 최소값과 top값일 때의 높이값의 차로 지정됩니다.
• 거리 * 높이값이 volume값에 추가됩니다.
• while문의 수행이 끝난다면 다시 한번 while문의 조건이 true인지 체크하고 참일 경우 다시 수행하면서 스택을 쌓아나갑니다.
• 밑의 그림과 같은 순서대로 volume 값이 커집니다. (3,4,5는 한번에 저장됩니다.)

• 두 풀이의 시간 복잡도는 O(n)으로 실행 시간은 비슷합니다.