[파이썬 알고리즘 인터뷰] - 7장 (배열) - 빗물트래핑

 

 

 

 

 

 

 

 문제

 

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

 

- 입력 

=> [0,1,0,2,1,0,1,3,2,1,2,1]

 

- 출력 => 6

 

 

 

 

 

 

 문제 상황

 

- 높이와 너비 모든 공간을 체크하면 O(N^2)로 풀이가 가능하지만 O(N)으로 속도를 줄일 수 있다.

 

 

 

 

 

 

 해결 전략

 

- 크게 투포인터 방식과 스택을 이용한 방식이 있다.

 

 

 

 

 

 

 코드

 

def solution(heights:list) -> int:
    left, right = 0, len(heights)-1
    leftmax, rightmax = 0, 0
    water = 0 # 총 물의 양
    # index left가 right보다 왼쪽에 있을 동안 반복
    while left <= right:
        leftmax = max(heights[left], leftmax)
        rightmax = max(heights[right], rightmax)
        
        if leftmax <= rightmax:
            water += leftmax - heights[left]
            left += 1
        else : 
            water += rightmax - heights[right]
            right -= 1
    return water

 

 

 

 

 

 

 

 

 해설

 

- 목적은 양쪽 끝에서 가장 높이가 큰 쪽으로 오는 것이다. 조건이 직관적으로 와닿지 않는다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 다시 풀이 필요