Leetcode 42. Trapping rainwater with Python - 리뷰 O

본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.

문제

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

n개의 음이 아닌 정수가 각각 너비가 1인 elevation map을 형성합니다, 이곳에 비가 내릴때 가둬질 물의 양을 구하세요

예시

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 파란 부분이 물이 찬 부분. 한칸마다 1의 공간을 가짐.

제한

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

풀이법

1. MY OWN

내가 생각해낸 방법은 물리엔진을 계산하듯 왼쪽과 오른쪽에서 가둬지지 않은 부분을 x로 표시한 뒤 표시되지 않은 부분을 전부 몇개인지 확인 하는 방법이였습니다.

def trapping(rains):
    maxHeight = max(rains)
    water = 0
    for i in range(0, maxHeight):
        temp = list()
        for j in rains:
            if i < j:
                temp.append(1)
            else:
                temp.append(0)
        for j in range(0, len(rains)):
            if temp[j] != 1: temp[j] = 2
            else: break
        for j in range(len(rains)-1, 0, -1):
            if temp[j] != 1: temp[j] = 2
            else: break
        for j in range(0, len(rains)):
            if temp[j] == 0: water += 1
    return water
    

가둬지지 않은 부분을 2로 표시하고 벽은 1로 표시하고 나머지는 0으로 표시한 뒤 0으로 표시된 부분의 갯수를 더했습니다.

시간복잡도는 최대 높이가 m이고 길이가 n일때 O(m*n) 입니다.

2. BRUTE FORCE

한 index에서 가둬질수 있는 물의 양은 왼쪽 벽의 최대 크기와 오른쪽 벽의 최대크기 중 최솟값에 자신의 높이를 뺀 값입니다.

이를 전부 더하게 합니다.

물론 자신의 물의 양이 음수가 나올시 이는 더하지 않습니다.

def trapping(rains):
    water = 0
    for i in range(1, len(rains)-1):
        lMax = max(rains[:i])
        rMax = max(rains[i+1:])
        if lMax == 0 or rMax == 0 or min(lMax, rMax) - rains[i] < 0: continue
        water += min(lMax, rMax) - rains[i]
    return water
    

시간복잡도는 길이가 n일때 안에서 max를 구하기 위해 또 O(n) 연산이 진행 되므로 O(n^2) 입니다.

3. SHIFTING POINTER

먼저 맨 왼쪽과 맨 오른쪽에 pointer를 위치합니다.

또한 maxLeft와 maxRight 변수를 0으로 선언합니다.

왼쪽이나 오른쪽 둘중 작은값이 있는 포인터의 경우, 아래와 같은 연산을 합니다.

이동 하기 전 자신에 상응하는 max 변수가 자신보다 작을경우 이를 자신의 값으로 치환합니다.

중요한것은 자신에 상응하는 max 변수보다 자신의 값이 작을 경우입니다.

일단 이동을 한다는것 자체부터가 값이 더 작다는 이야기이고,
반대편에 상응하는 값이 자신보다 크고 왼쪽에서 온 값보다도 클 것이라는 것입니다.
즉 반대편에 큰 벽이 있다는 것입니다.

자신의 방향에서의 max값보다 자신이 작다는 것은 그 방향에는 반대방향보다는 작지만 벽이 존재한다는 것이기에 brute force의 왼쪽 벽의 최대 크기와 오른쪽 벽의 최대크기 중 최솟값은 곧 상응하는 max값이라는것을 알게 됩니다.

즉 상응하는 max변수 - 자신의 높이 만큼을 물의 총량에 더하고 포인터를 안쪽으로 이동시키면 됩니다.

코드는 다음과 같습니다.

def trapping(rains):
water = 0

# 포인터 위치
left = 0
right = len(rains) - 1

# max값
maxLeft = 0
maxRight = 0


while left != right:

    # 값이 작은쪽이 안쪽으로 이동
    if rains[left] < rains[right]:

        # 자신의 값이 max값보다 크다면 -> max에 대입하고 안쪽 이동
        if maxLeft <= rains[left]:
            maxLeft = rains[left]
            left += 1

        # 자신의 값이 max보다 작다면 -> 반대쪽 max는 자기쪽 max보다 큰것은 확실하기에, 
        # 자신의 max값이 곧 양쪽 벽 최댓값 둘중 작은 값임. 
        # 이 값에 자신의 높이를 빼준 값을 총 water에 더해준다.
        else:
            water += maxLeft - rains[left]
            left += 1

    # 반대편은 그냥 변수명만 바꿔주면 됨.
    else:
        if maxRight <= rains[right]:
            maxRight = rains[right]
            right -= 1
        else:
            water += maxRight - rains[right]
            right -= 1
return water

shifting pointer를 이용해 O(n)의 시간복잡도와 O(1)의 공간복잡도로 문제를 해결할수 있었습니다.

( 2024/11/19 )

복기

• 직접적인 투포인터는 죽어도 쓰기 싫어서 양쪽으로 스택 순회하는 방식으로 한번 풀어봤다.

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

        ans = 0

        for h in height:
            if not s:
                s.append(h)
            else:
                if s[0] <= h:
                    while len(s) > 1:
                        ans += s[0] - s.pop()
                    s.pop()
                s.append(h)


        ss = []

        for h in reversed(s):
            if not ss:
                ss.append(h)
            else:
                if ss[0] <= h:
                    while len(ss) > 1:
                        ans += ss[0] - ss.pop()
                    ss.pop()
                ss.append(h)

        return ans

• 이후에 예전 답 보고 변수를 좀 더 정리해서 다시 풀어봤다.
• 왼쪽이 오른쪽보다 작다는것은 오른쪽에 의해 무조건 막히긴 한다는 의미이기 때문에 가능한 것

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

        left = 0
        right = len(height) - 1

        max_left = 0
        max_right = 0

        while left < right:
            height_left = height[left]
            height_right = height[right]

            if height_left < height_right:
                if max_left < height_left:
                    max_left = height_left
                else:
                    ans += max_left - height_left
                left += 1
            else:
                if max_right < height_right:
                    max_right = height_right
                else:
                    ans += max_right - height_right
                right -= 1

        return ans

• 전반적으로 가독성을 조금 향상시키려 했다.

단일 스택 풀이법

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

        for i, h in enumerate(height):
            while s and height[s[-1]] < h:
                bottom = s.pop()

                if not s:
                    break

                left = s[-1]
                ww = i - left - 1
                hh = min(height[left], h) - height[bottom]
                ans += ww * hh
            s.append(i)

        return ans

• 물구덩이가 생기자 마자 최대한 빠르게 계산하는것이 포인트이다.
• 스택은 오른쪽이 막혀 ( 오른쪽이 더 커서 ) 물구덩이가 생겼을때 바로 왼쪽 바닥의 왼쪽에 있는것이다.
• 만약 왼쪽 바닥의 왼쪽도 작다면 어차피 더하는 값이 0이 될것이고, 더 왼쪽으로 탐색해 나간다.