날짜: 2021년 8월 24일
카테고리: 배열
태그: Hard, 42, 파이썬

leetcode 42 - Trapping Rain Water

입출력 예시

코드

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

        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                ex_height_idx = stack.pop()

                if not len(stack):
                    break

                distance = i - stack[-1] -1
                waters = min(height[i], height[stack[-1]]) - height[ex_height_idx]

                volume += distance * waters

            stack.append(i)

        return volume

풀이 과정

배열 height의 길이만큼 반복하기 위해 for문을 사용

stack안에 원소가 있으면서, i인덱스의 height의 크기(현재 비교할 높이)가 stack[-1] 인덱스의 height의 크기(물이 고일 공간이 생길 만한 이전의 높이)보다 커질 때
ex_height_idx에 현재 스택 가장 상위 원소(바로 직전의 높이 인덱스)를 pop하고,

만약 스택에 원소가 없다면, 물이 고일 공간이 생기는 이전의 높이가 없다는 뜻이기 때문에 break하여 while문을 나감

현재 비교할 높이의 인덱스인 i에서 물이 고일 공간이 생길 만한 이전의 높이의 인덱스인 stack[-1]를 뺀 값에 -1을 한 값(물이 고여있는 거리)을 distance에 저장
height[stack[-1]](이전의 높이)과 height[i](현재의 높이) 중 더 낮은 곳에서 height[ex_height_idx]를 뺀 값(물이 고여있는 깊이)을 waters에 저장

물의 양을 나타내는 volume에 물이 고여있는 거리 distance와 물이 고여있는 깊이 waters를 곱한 값을 계속 더해 줌

stack에 현재 위치 i를 저장 (다음 고여있는 물의 양 계산 시 이전의 높이가 됨)

i가 height배열 마지막 인덱스에 도달할 때 까지 반복 후 volume 반환

반성

• 스택에 대해서는 완벽하게 이해했다고 생각했는데 이 문제를 스택으로 풀 수 있다는 것을 유튜브로 강의를 보기 전까지 코드를 보고도 이해를 못했다. 좀 더 많이 풀어보자