[leetcode][Hard][Two Pointers] 42. Trapping Rain Water 풀이, 해설 (python) : 해설 참고해서 푼 풀이

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

Trapping Rain Water - LeetCode

 

한시간 정도 풀릴까 말까 하다가, 풀리지 않아서 ... 

결국 해설을 본 풀이이다. 

 

일단, trap을 계산할때 2가지 케이스가 있는 것으로 확인했다. 

물이 갇히는 구역을 잘 나눴다는 가정하에, 왼쪽과 오른쪽의 최소값을 기준으로 물의 양을 계산할 수 있다는 것이다. 

2가지 케이스 : min(l,h) - h[i]

그래서 영역을 잘 나누기만 하면 계산할 수 있을 것 같았는데, 그 부분에서 뭔가 코드가 꼬였는지 해결이 어려웠다. 

풀다가 중도포기한 코드를 기록차 공유한다. 

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        limit = height[0]
        start = 0 
        trap = 0
        for end in range(1, len(height) - 1):
            h = height[end]
            if h > limit:
                length = min(height[start], height[end])
                t = end - 1
                while t >= start:
                    if length > height[t]:
                        trap += (length - height[t])
                    print('..', t, trap, length)
                    t -= 1 
                
                # 다음 목록 조회 
                start = end + 1
                limit = height[start]
            else : 
                # 다음 높이로 이동 
                limit = h
            
            # print(end, trap)
            
            
                
        
        return trap

 

해설

https://www.youtube.com/watch?v=ZI2z5pq0TqA

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        if not height:
            return 0 
        
        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0 
        
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1 
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
            
    
        
        return res

해설은 각각 왼쪽과 오른쪽의 minLeft와 maxRight를 계산해서, 포인터를 이동하면서 계산했다. 

chatgpt 통해서 for문으로 바꾸면 다음과 같은 풀이도 가능하다. 사실상 for문에 사용한 i는 의미가 없다. 

left, right = 0, len(height) - 1
leftMax, rightMax = height[left], height[right]
res = 0

for i in range(len(height)):
    if leftMax < rightMax:
        leftMax = max(leftMax, height[left])
        res += leftMax - height[left]
        left += 1
    else:
        rightMax = max(rightMax, height[right])
        res += rightMax - height[right]
        right -= 1

 

아래와 같이 예시를 통해 이해하면 좀 더 쉽게 이해할 수 있다. 

 

아무래도 Hard난이도 문제는 아직 어려운 것 같다. 

다음번에 다시 시도해봐야겠다.