[1스4코2파] # 183. LeetCode 42. Trapping Rain Water

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (183차)
[4코1파] 2023.01.13~ (175일차)
[1스4코1파] 2023.04.12~ (86일차)
[1스4코2파] 2023.05.03 ~ (64일차)

Today :

2023.07.05 [183일차]
LeetCode Patterns
42. Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/

42. Trapping Rain Water

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

문제 설명

음이 아닌 정수로 구성된 높이를 나타내는 배열이 주어졌을 때 비가 온 후 담기게 될 물의 양을 구하는 문제이고, 각 폭은 1임.

문제 풀이 방법

주어진 height들의 array 들이 있을 때, 사이에 담기는 비의 최종 값을 return 한다. 비가 담기는 범위는 자신의 양쪽에 대해 가장 높은 벽들이 기준임
two pointer로 풀었고, time complxity O(n), space complexity O(n) 풀이도 있고, space complexity O(1) 인 풀이도 있는데 일단 난 둘다 O(n) 것만 이해했다.
brute force로 푸는 방법도 있지만 그건 시간복잡도가 O(n^2)이다.

물은 현재 기준 왼쪽과 오른쪽 bar의 가장 낮은 위치까지 밖에 담기지 못한다.
그러므로 현재 위치 기준에서 left와 right에서 가장 낮은 높이에다가 현재 위치의 height를 빼주면 물의 부피가 나온다.

내 코드

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        maxLeft = [0 for _ in range(n)]
        maxRight = [0 for _ in range(n)]
        ans = []

        for i in range(1, n):
            curmax = max(maxLeft[i-1], height[i-1])
            maxLeft[i] = curmax
        
        for j in range(n-2, -1, -1):
            curmax = max(maxRight[j+1], height[j+1])
            maxRight[j] = curmax

        for k in range(n):
            water = min(maxLeft[k], maxRight[k])- height[k]
            if water <0:
                ans.append(0)
            else:
                ans.append(water)

        return sum(ans)

증빙

여담

박대갈 나의 노력 이해완