Algorithm Problem with Python — 33day
문제 설명 📖
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
각 막대의 너비가 1인 입면도를 나타내는 n개의 음이 아닌 정수가 주어지면 비가 내린 후 얼마나 많은 물을 가둘 수 있는지 계산한다.
제한사항⁵
- n == height.length
- 0 <= n <= 3 * 10⁴
- 0 <= height[i] <= 10⁵
입출력 예
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
문제 이해 🔑
이 문제는 투 포인터를 최대로 이동하는 방법과 스택을 쌓는 방법으로 해결할 수 있습니다.
저는 투 포인트를 최대로 이동하는 방법으로 진행했습니다.
먼저 가장 높이가 높은 막대를 살펴보면 예시 1에서 최대 높이가 3이지만 최대 높이라는 역할을 한다면 값에 무관하게 전체 부피에 영향은 끼치지 않습니다.
그저 왼쪽과 오른쪽을 가르는 장벽 역할을 합니다.
가장 높이가 높은 막대를 기준으로 좌우로 투 포인트를 배치하고 기준까지 이동하며 부피를 체크합니다.
기준이 되는 최대 높이 막대까지 각각 좌우 기둥 최대 높이와 현재 높이와의 차이만큼 물 높이를 더해 나가면 됩니다.
수도 코드 ✍️
- 제한 사항 '0 <= n <= 3 * 10⁴'을 보면 height가 0인 경우도 존재하니 예외처리를 먼저 합니다.
- 가장 높은 막대 기준으로 좌우측을 체크하는 변수를 만듭니다.
- 좌우측에서 가장 높은 막대를 체크하는 변수를 만듭니다.
- 2번에서 만든 변수가 가장 높은 막대위치까지 오기 전까지 좌우 어느 쪽이든 낮은 쪽에서 높은 쪽을 향해서 포인터를 가운데로 점점 이동시킵니다.
코드 작성 ⌨️
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
volume = 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
while left < right:
left_max, right_max = max(height[left], left_max), max(height[right], right_max)
if left_max <= right_max:
volume += left_max - height[left]
left += 1
else:
volume += right_max - height[right]
right -= 1
return volume정리 😄
이번 문제는 상당히 어려웠습니다.
효율적인 풀이법을 못 찾고 높이와 너비 모든 공간을 차례대로 모두 살펴봤으면 0(n²)의 시간복잡도가 걸렸을 것입니다.
이번 풀이를 통해서 해당 문제와 같은 유형에서는 투 포인터나 스택으로 0(n) 풀이가 가능한 것을 알게 되었습니다.
최대 높이 막대가 기준이 되는 점을 통해 좌우로 나눌 수 있었고 좌우 각각에서도 가장 높은 막대와 현재 막대 높이의 차이만큼 물 높이가 생기는 것을 알 수 있었습니다.
복잡한 문제일수록 문제를 잘게 나누어 고민하면 이와 같이 풀어 나갈 수 있으니 복잡함을 단순함으로 나누는 연습이 필요함을 느낄 수 있는 문제였습니다.
Reference
- 박상길, 『파이썬 알고리즘 인터뷰, 책만 (2020), p180-183.
