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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

높이에 따라 쌓일 수 있는 물의 총계 계산

 

책에서 구현된 코드

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

 

기억해야할 기법

• 문제를 해결하는 기준으로 '최대값' 활용하기
  • 최대값을 기준으로 좌우에서 투포인터로 계산
• 스택으로 푸는 방법은 코드를 봐도 이해를 못함

 

내가 구현한 코드

None

• 오래 생각해도 풀이를 생각하기 어려운 문제였다
• 특히 스택을 응용하는 방법은 앞으로도 응용할 수 있을지 모르겠다

def trap(height: list[int]) -> int:
    stack = []
    volume = 0

    for i in range(len(height)):
        # stack에 값이 있고, top의 값이 낮아야 물이 찰 수 있음
        while stack and height[i] > height[stack[-1]]:
            
            top = stack.pop()
			# 3개 이상을 비교해야 가운데 물이 찰 수 있음
            if not len(stack):
                break

			# 마지막 max값과의 거리
            distance = i - stack[-1] - 1
            # 마지막 max값과 현재값 중 더 낮은 높이로 물이 참
            # top의 높이만큼 물이 덜 참
            # top 이전의 높이가 일정하지 않은데, 이미 이전 물의 양은 계산됨
            waters = min(height[i], height[stack[-1]]) - height[top]

            volume += distance * waters

		# 확인을 마친 인덱스는 무조건 push
        stack.append(i)
    return volume