[TIL] 👨‍💻파이썬 알고리즘 인터뷰 Day_2 # 배열 빗물 트래핑

🤴Day 2 Array Trapping rain water

 

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

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

 

08번 문항인 빗물 트래핑 문제이다. 리트코드 42번 문제로 블럭 사이에 고일 수 있는 물의 양을 계산하는 문제이다.

1. 무작정 비교하며 적층하면서 풀기

#First Method
class Solution:
    def trap(self, height: List[int]) -> int:
        
        water = 0
        
        for i in range(1, len(height)):

            
            left = height[i]

            for j in range(i):

                left = max(left,height[j])

            right = height[i]

            for j in range(i+1,len(height)):

                right = max(right,height[j])

            water = water + (min(left,right)-height[i])
        
        return water

Time Limit Exceeded
위 방법으로 폴었더니 시간이 초과되어 실패하였다.
좀 더 효율적인 방법으로 Stack을 사용하기로 하였다.

도전 실패..

2. Stack 사용

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

        n = len(height) 

        left = [0]*n

        right = [0]*n

        left[0] = height[0]

        for i in range(1,n):
            left[i] = max(left[i-1], height[i])

        right[n-1] = height[n-1]

        for i in range(n-2,-1,-1):
            right[i] = max(right[i+1],height[i])

        for i in range(n):
            water += min(left[i],right[i]) - height[i]

        return water

이 방법으로는 IDE에서 푸는데 성공하였지만 왜인지 모르게 Leetcode에서는 에러가 뜨게 되었다. 마지막으로 책에 있는 방법으로 접근해보았다.

3. 투포인터

def trap(self,height: List[int]) -> int:  
    if not height:  
        return 0  
  
    water = 0  

    left, right = 0, len(height) - 1 # 투포인터는 처음과 마지막을 설정하고 좁혀가는 방식  

    max_left, max_right = height[left], height[right] # 초기값 설정  

    while left < right: # left, right 둘이 점점 붙게 한다.  
    max_left, max_right = max(height[left], max_left), max(height[right], max_right)  

          if max_left <= max_right:  
              water += max_left - height[left]  
              left += 1  
    else:  
              water += max_right - height[right]  
              right -= 1  
    return water

지난번에도 투포인터에 대해 알아가면서 투포인터는 기본적으로 left, right을 각각 처음값과 끝값을 잡은 후 while left < right 가 될 때 까지 순회하면서 간격을 좁혀나가는 방식이라는 것을 알 수 있었다.

4. Stack 활용(In Book)

from typing import List

class Solution:

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

마지막 방법은 코딩 초보인 나로서는 도저히 생각이 안나서 완전히 베꼈다.

Summary

빗물 트래핑 문제는 본 책에서 난이도 상의 문제이다. 무작정 적층하는 방식은 구현하기 쉬웠지만 복잡도가 $O(n^2)$이 되므로 바로 실패하였고, 결국 투포인터나 스택을 이용해서 접근해야 한다는 것을 알았다.

Written with StackEdit.