leetcode42. Trapping Rain Water 빗물 트래핑 문제풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

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

입력: 땅에 쌓아올린 벽돌의 높이를 기록한 리스트

출력: 물이 고인 양을 합한 양의 정수 

 

문제 요약: 그림으로 그리면 이해가 쉽다.

예제 1번은 [0,1,0,2,1,0,1,3,2,1,2,1]인데, 이를 그림으로 그리면 아래의 검은 블록과 같고, 물이 고인 양은 파란색의 합과 같다.

 

유의 사항: 제일 처음과 제일 마지막 블록은 고인 물이 무조건 0이 될 수 밖에 없다. 양쪽에 벽이 있어야 물이 고일 수 있기 때문

 

생각 과정

먼저 for 문으로 전체를 한 번 탐색하는 풀이 방법을 생각했다.

답은 잘 나왔지만, 속도가 너무 느려서 하위 5% 밖에 안되는 문제가 있었다.

그랬지만, 비교적 이해가 쉬워서 금방 풀이를 짤 수 있었다.

내가 i 번 째에 있다면 내 왼쪽에서 최고 높은 벽돌, 오른쪽에서 최고 높은 벽돌을 찾고, 이중에서 낮은 것과 내 벽돌 높이의 차이 만큼이 내 위치에 고인 물의 양이 된다.

즉 min(max(height[:i]), max(heigh[i:])) 와 height[i]의 차이가 그 자리에 물이 고인 양이고, (물론 그 차가 0보다 클 때만) 이를 전체 다 더하면 output이 된다.

class Solution:
    def trap(self, height: List[int]) -> int:
        answer = [0]*len(height)
        for i in range(1, len(height)-1):
            h_diff = min(max(height[:i]),max(height[i:]))
            if h_diff-height[i] > 0:
                answer[i]=h_diff-height[i]
        return sum(answer)

이렇게 하면 통과는 하지만, 하위 5%라고 뜬다.

for 문이 아닌 while 문으로 해결할 수 없는지 고민해봐야 하는 것이다. 

풀이

 

*참고*

사실 책의 앞부분(7장)에 나오지만, 잘 이해하지 못해서 포스팅하지 못하다가 나중에 다시 한 번 보고 조금은 이해하게 된 문제.

여전히 스스로의 힘으로 풀기는 어려웠고, <파이썬 알고리즘 인터뷰> 책과 유튜브 해설 동영상을 참고하여 이해했다.

내가 참고한 동영상

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