[LeetCode] 42. 빗물 트래핑(Trapping Rain Water)

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

 

 

1. 내가 직접 푼 코드

 

...

 

해설:

 

너무 어려워서 풀다 포기함..

 

 

** 깔끔한 답안 **

 

2. 투 포인터를 최대로 이동

 

class Solution:
    def trap(self, height: List[int]) -> int:
            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

 

해설:

 

어딘가에 최대 높이의 막대가 있다고 가정하고 

left와 right 포인터로 중간으로 이동하다 보면 최대 높이의 막대에서 두 포인터가 만날 것이다.

 

그림과 같이 left의 경우,

 left_max와 그보다 작은 높이의 차이를 쭉쭉 구해나간다.

(그러면서 volume에 그 값이 더해진다)
left_max < right_max인 경우 right_max가 최대 높이일 확률이 있으니

 left 포인터가 이동해야 한다.

(right_max가 최대 높이라면 right 포인터는 더 이동할 필요가 없으니까)
그러다 left는 최대 높이에 도달하고 이제는 right가 중간으로 이동해나간다. 

그러면서 right에서의 volume도 더해나간다.

 

 

2. 스택 쌓기

 

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 stack:
                    break
 
                # 이전과의 차이만큼 물 높이 처리
                distance = i - stack[-1] - 1
                waters = min(height[i], height[stack[-1]]) - height[top]
                volume += distance * waters
 
            stack.append(i)
        return volume

cs

 

해설:

 

답을 봐도 한 번에 이해가 가지 않는 어려운 풀이였다.

풀이가 결국 이해는 가지만 내가 이걸 다시 만났을 때 풀 수 있을까?라는 의문이 들었다..ㅋ

일단은 이해한 것을 설명해보면...

요점은 현재 높이가 이전 높이보다 높을 때, 즉 변곡점을 기준으로 격차만큼 물 높이를 채우는 것이다.

예시의 그림을 들고 와 설명해보면

 

 

인덱스 1의 경우 이전 높이보다 높지만 스택에 쌓여있는 게 없어서 물이 안 채워지고

인덱스 3에서는 이전 높이보다 높고 스택에 인덱스 1,2이 채워져 있는 상태에서

인덱스 2를 top에 대입하고(pop 해서 스택에서 빠짐) 인덱스 1(stack [-1])과 인덱스 3의 거리를 생각하면 1,

두 인덱스의 최소 높이는 1인데 height [top]은 0이므로 거리*높이=1이 된다

따라서 인덱스 1과 인덱스 3 사이의 물의 계산이 해결된다.

다시 while의 시작으로 돌아가서 stack.pop()을 하면 stack이 비므로 while문 탈출.

 

어렵냐? 나도 어렵다..

대충 이런 식으로 stack을 쌓다가 이전보다 높은 막대를 만나면

물을 계산하면서 stack을 싹 비워주는거다.

스택 쌓고 비우고 쌓고 비우고의 반복~

 

이제 인덱스 3과 인덱스 7 사이의 물을 계산해보자...ㅅㅂ..

우선 앞에서 스택을 다 소비했고 인덱스 3만 스택에 들어있는 상황.

인덱스 4, 인덱스 5 모두 이전 높이보다 낮아서 아무것도 못하고 스택에 저장됨..

인덱스 6에서 드디어 이전 높이보다 높다.

그럼 인덱스 5를 top에 할당하고

스택에 젤 마지막에 저장된 인덱스 4와 인덱스 6의 거리를 생각하면 1,

두 인덱스의 최소 높이는 1이고 height [top]은 0이므로 거리*높이=1이 된다.

이 부분의 물을 구했다

 

스택에는 인덱스 3,4 그리고 6이 쌓여있고 다음 인덱스 7은 이전보다 높다!

따라서 인덱스 6이 top에 할당되고 인덱스 4와 인덱스 7의 최소 높이는 1,

거리는 3이니까 거리*높이=3이 된다.

이 부분의 물을 구했다

 

이런 식으로 물을 계속 구하면서 끝까지 가면 된다...

 

스택을 이 문제에 적용하는 게 상당히 어렵다...

이걸 시험장에서 꺼내서 쓰려면 상당한 내공이 필요할 듯..

한 문제를 다양한 방식으로 풀 줄 알아야 나중에 어떤 문제를 만났을 때

어떤 무기로 썰어버릴까~ 하면서 고민할 수 있다.

무기를 다양하게 해 놔야 무가 나오면 식칼로, 회가 나오면 사시미로 썰 수 있다 ㅎ

마지막으로 지금까지 본 개념을 바탕으로 스스로 한 번 코딩해보자.

 

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]