리트코드_42 빗물 트래핑_Hard (투포인터_NHN 기출 동일문제)

• 링크 : https://leetcode.com/problems/trapping-rain-water/
  • 예전에 NHN 기출 풀 때 풀었던 문제랑 동일

메모

이거 전에 NHN 기출 풀 때 풀었던 문제랑 동일

• 링크 : https://velog.io/@taehyeon96/백준14719-빗물

건물의 높이들을 리스트로 입력받고
그안에 틈이 있으면 얼만큼의 물이 채워지는지 계산하는 문제

알고리즘 및 방법

mm <- max높이 저장해둠
각각 양쪽 끝에서 투포인터로 mm까지 이동하면서
자기보다 낮은 건물이면 ans += (현위치 - 낮은 위치 = 매 순간의 물)
자기랑 같거나 높은 건물이면 현위치 갱신

left와 right 구분해서 mm까지만 이동하는 것으로 진행 + 투포인터 사용

left, right = 0, len(arr)           # cur 용 인덱스 위치 (포인터 1)

# 왼쪽부터
for i in range(0 to (mm + 1)):      # i는 이동하는 위치 (포인터 2)
    if arr[cur] > arr[i]:           # 낮아지는 구간
        water += (arr[cur]-arr[i])  # (기준 위치와 낮아진 만큼의 차)를 더해줌
        
    elif arr[cur] <= arr[i]:        # 높아지는 구간
        cur = i                     # 물을 채우는 기준 위치 갱신
    
# 반대로 오른쪽부터
for i in range(len() to mm):
    ~

---

책 해설 (중요)

• 이 문제는 높이와 너비 모든 공간을 차례대로 살피면 O(n^2)에 풀이가 가능하다

  • 하지만 이 경우, 시간복잡도가 너무 높아 효율적인 풀이가 필요

• 투포인터나 스택으로 O(n)에 풀이가 가능하다

• 책의 투포인터 풀이

  • 먼저 예제에서 가장 높은 벽을 봐보자. 최대 높이는 3이지만 100이어도 상관없다.
  • 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 함
  • 아래 코드는 최대 높이까지 좌우 각각의 최대 기둥 높이(left_max, right_max)가 현재 높이와의 차이만큼 물 높이 volume을 더해나감

volume += left_max - height[left]
...
volume += right_max - height[right]

• 그리고 아래 코드를 통해 낮은 쪽은 그만큼 항상 채워질 것이므로
  • 좌우 어느 쪽이든 낮은 쪽은 높은 쪽을 향해 포인터가 가운데로 점점 이동함
  • 오른쪽이 크다면 left += 1로 왼쪽이 이동하고
  • 왼쪽이 크다면 right -= 1로 오른쪽이 이동한다.

if left_max <= right_max:
    water += left_max - height[left]
    left += 1
else:
    water += right_max - height[right]
    right -= 1

• 이후 두 포인터가 가장 높은 막대(=최대 지점)에서 만나 O(n)에 풀이가 가능하다!

---

---

솔루션 코드 - 내가 푼

• 예전 NHN 풀었을 때 방식 기억 더듬어서 바로 품
  • 당시엔 투포인터 방법인지는 몰랐네

class Solution:
    def trap(self, arr: List[int]) -> int:
        left, right = 0, len(arr)-1
        
        mm = arr.index(max(arr))        # (중요!!!) max의 인덱스를 저장해야함
        water = 0
        
        # 왼쪽 투포인터 진행
        for i in range(0, mm + 1):
            if arr[left] > arr[i]:
                water += (arr[left] - arr[i])
            elif arr[left] <= arr[i]:
                left = i        
        
        # 오른쪽 투포인터 진행
        for i in range(right, mm, -1):
            if arr[right] > arr[i]:
                water += (arr[right] - arr[i])
            elif arr[right] <= arr[i]:
                right = i
        
        return water

• 테케 1 진행 과정 설명
  • 투포인터가 이동하는 인덱스랑 그에대한 value값

left 높이 || i  높이 || water
0    0   || 0   0   || 0
0    0   || 1   1   || 0
1    1   || 2   0   || 0
1    1   || 3   2   || 1
3    2   || 4   1   || 1
3    2   || 5   0   || 2
3    2   || 6   1   || 4
3    2   || 7   3   || 5
물 : 5

right 높이 || i  높이 || water
7      3  || 11   1  || 5
7      3  || 10   2  || 5
7      3  || 9    1  || 5
7      3  || 8    2  || 6
최종 물 : 6

---

솔루션 코드 - 책1

• 투포인터 방법
• 나랑 달리 동시에 이동 -> 시간적으로 더 단축일듯

def trap(height):
    if len(height) < 1:
        return 0

    water = 0
    left = 0
    right = len(height) - 1
    
    left_max = height[left]
    right_max = height[right]
    
    while left < right:
        left_max = max(height[left], left_max)
        right_max = max(height[right], right_max)
        
        if left_max <= right_max:
            water += left_max - height[left]
            left += 1
        else:
            water += right_max - height[right]
            right -= 1
        
    return water

---

솔루션 코드 - 책2

• "스택 쌓기" 풀이
  • 왼쪽 오른쪽 구분 안하고, 앞에서부터 끝까지 쭉 진행함
  • 현재 높이가 이전 높이보다 높을 때(=꺾이는 변곡점)을 기준으로 volume을 +=
  • 투포인터와 마찬가지로 O(n)에 해당함
  • 나도 변곡점을 기준으로 왼/오 나눠서 진행한건데 이거랑 다를게 없지않나

def trap(height):
    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