[리트코드(LeetCode)] 42. Trapping Rain Water - Python

leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

 

풀이 1. 투 포인터를 이용

두 개의 포인터가 각각 리스트의 좌, 우에서 시작한다.

현재 포인터가 가리키고 있는 인덱스를 left, right에 저장하고, 포인터가 지나왔던 자리 중 가장 높았던 값을 left_max, right_max에  저장한다.

 

두 포인터가 만날 때까지 while문을 돌게 되는데, left_max와 right_max의 값을 매번 포인터가 이동할 때마다 해당 포인터의 자리의 높이와 비교를 해서 업데이트를 시킨다.

 

left_max와 right_max 중 낮은 값을 가진 쪽의 포인터를 이동시킨다. 이 때 해당 위치에서 쌓이는 물을 그때그때 volume에 저장한다.

left는 좌에서 우로, right는 우에서 좌로 이동하면서 결국 가장 높은 지점에서 두 포인터가 만나 끝이 나게 된다.

from typing import List

class Solution:

    # 풀이 1. 투 포인터를 최대로 이동
    def trap_twoPointer(self, height: List[int]) -> int:
        if not height:
            return 0

        volume = 0

        left, right = 0, len(height) - 1
        left_max, right_max = height[0], height[right]

        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])

            # 더 높은 쪽을 향해 투 포인터 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1

        return volume

 

풀이 2. 스택을 이용

stack에 height 값을 쌓다가 현재 위치보다 높아지는 변곡점을 기준으로 격차만큼 물 높이를 채운다.

투포인터가 종 방향으로 물을 면적을 추가했다면 스택은 변곡점과 스택의 값들 사이에서의 횡방향으로 물 면적을 나눠서 저장하게 된다.

from typing import List

class Solution:
	# 풀이 2. 스택 쌓기
    # height를 스택에 쌓아 가다가 변곡점(현재 보다 높아질 때)을 기준으로 격차만큼 물 높이 volume을 채움
    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 len(stack):
                    break

                # 이전과의 차이만큼 물 높이 처리
                distance = i - stack[-1] - 1
                waters = min(height[i], height[stack[-1]]) - height[top]
                volume += distance * waters

            stack.append(i)

        return volume

(스택 같은 경우는 직관적으로 떠올리기 쉽지 않을 듯하다..)

 

 

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

파이썬 알고리즘 인터뷰 - 교보문고