[leet42] 두 개의 포인터, 한 개씩 이동하자

leetcode 42. Trapping Rain Water

위 문제처럼 가운데 container의 넓이를 구하는 식의 문제에서는 양 끝단에 두 개의 pointer를 두고 안쪽으로 좁혀가면서 넓이를 구한다. 우선 이런 식의 접근을 외워뒀다가 먼저 염두에 두는 편이 편하다.
이번 42번 문제도 마찬가지이지만, 양 포인터에서 동시에 한칸씩 이동하다가 한참을 헤맸다. 두 포인터가 만났을 때 양쪽에서 진행하던 max_height가 다르기 때문에 예외 처리해줘야할 사항이 한둘이 아니었기 때문이다. 한 칸씩 이동하는 방식으로 바꾸었더니 정말 쉽게 풀렸다.

Question

Solution

PSEUDO

• 양끝 투 포인터 사용

• left<right 동안 왼/오 중 작은쪽에서 한칸씩 이동하면서 아래 작업 수행

• height[left+1] < left_max: (더 낮아진다면)
  left_temp += left_max-height[left+1]

• else: (더 커지거나 같다면, temp 정산)
  ans += left_temp
  left_temp = 0
  left_max = height[left+1]
  left += 1

• (right에서도 마찬가지로 수행)

• 마지막에 한쪽에서 이동해서 만나게 되면 ans + left_temp + right_temp 모두 더해줘서 return

아마 temp가 필요 없이 바로 ans에 더해줘도 괜찮을 것 같음
양쪽에서 동시에 한칸씩 이동한다면 둘의 max값들이 다르기 때문에 가운데에서 복잡해질 수 있음. (문제 풀기 어려움) 한칸씩만!!

from typing import List

def trap(height: List[int]) -> int:
    if len(height) <= 2: return 0

    left_idx = 0
    right_idx = len(height)-1
    ans = 0
    left_temp, right_temp = 0, 0
    left_max, right_max = height[0], height[-1]

    while left_idx < right_idx:
        if left_max <= right_max:
            if height[left_idx+1] < left_max:
                left_temp += (left_max - height[left_idx+1])
            else:
                ans += left_temp
                left_temp = 0
                left_max = height[left_idx+1]
            left_idx += 1
        else:
            if height[right_idx-1] < right_max:
                right_temp += (right_max - height[right_idx-1])
            else:
                ans += right_temp
                right_temp = 0
                right_max = height[right_idx-1]
            right_idx -= 1
    return ans + left_temp + right_temp

github