리트코드 Tapping Rain Water

문제링크 : https://leetcode.com/problems/trapping-rain-water/

비슷하지만 비교적 쉬운 백준 링크 : https://www.acmicpc.net/problem/14719

문제

 

빗물이 고이는 원리

빗물이 고이려면 현재위치의 높이를 기준으로
왼쪽과 오른쪽이 ‘현재 높이보다 높아야’ 한다

 

이때, 쌓이는 양은 min(왼쪽, 오른쪽) - 현재 위치의 높이 가 된다

 

height 전체를 확인하지않고, 결과를 확인할수 있는 방법이 있을까?

결론은 안될것같다.

 

빗물의 양을 구하는 곳에서는 총 3곳의 블록값을 보는데 ‘내 위치, 왼쪽, 오른쪽' 이 되는데
주어지는 height 블록의 리스트 값이 모두 다르기 때문에
각 좌표의 블록값에 맞추어서 찾는것이 맞는것같다

 

백준에선 뚫리고, 리트코드에선 안뚫리는 소스코드

height = [0,1,0,2,1,0,1,3,2,1,2,1] 
W = len(height)
answer = 0
for i in range(1, W-1):
    left_block = max(height[ :i]) #내 왼쪽에서 제일 높은벽
    right_block = max(height[i+1: ]) #내 오른쪽에서 제일 높은벽 

    minimum = min(left_block, right_block) #어차피 높이는 둘중 낮은값만큼 쌓임

    if minimum > height[i]: #나보다 높은벽들 사이에 있다면
        answer += minimum - height[i]

print( answer )

현재 위치를 기준으로, 왼쪽에서 가장 높은벽, 오른쪽에서 가장 높은벽을 확인한다. 둘중 낮은값을 확인하고
내가 둘중 낮은값보다 낮은위치라면, 물을 쌓이는 방식이다

 

이 소스코드가 리트코드에서는 안뚫리는 이유는 left_block, right_block을 구하는 과정 때문이다max()를 쓰는데, 이때 인덱스 i 를 기준으로 ‘좌측의 모든 배열값' 과 ‘우측의 모든 배열값' 을 구하기 때문이고
구간을 절반씩 나누므로 O( n**2 / n) 이 되어서 결국 시간복잡도에서 터질것이다

 

리트코드에서도 뚫리는 소스코드

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        areas = 0
        max_l = max_r = 0
        l = 0
        r = len(height)-1
        while l < r:
            if height[l] < height[r]:
                if height[l] > max_l:
                    max_l = height[l]
                else:
                    areas += max_l - height[l]
                l +=1
            else:
                if height[r] > max_r:
                    max_r = height[r]
                else:
                    areas += max_r - height[r]
                r -=1
        return areas

투포인터를 써서 푸는 방식이다

좌, 우 에 포인터를 하나씩 두고, 각 위치의 높이값을 확인한다

왼쪽, 혹은 오른쪽을 기준으로 시작해서
왼쪽의 바로 왼쪽값, 오른쪽의 오른쪽 값을 확인하되
가장 높았던 왼쪽값, 가장 높았던 오른쪽 값을 가지고 있는다

 

이렇게하면 좋은점은 height[ : l] 혹은 height[r: ] 로 가장 높았던 값을 확인할 필요가 없어진다는거다.
리스트 인덱싱에 O(n)만큼 들어갈거고, 매 iteration만큼 돌테니까 길이가 L 이라면 O(n *L) 을 줄일수 있는것이다