🔦 문제 링크
🔊
파이썬 알고리즘 인터뷰책을 참고했습니다.
- 문제
높이를 비교하여 비 온후 얼마나 많은 양의 물이 쌓일 수 있는 지 구하라.
✍️ 풀이
- 투 포인터 활용
- 왼쪽과 오른쪽의 최대 장벽 높이를 구한다.
- 이 장벽에 도달할 때까지 한 쪽이 진행하게 된다.
- 진행하는 쪽은 진행하는 쪽의 최대 높이와 현재의 차이를 구해 빗물을 증가시킨다.
- 만약 진행하다가 최대 장벽을 차지하게 된다면 다른 한쪽이 진행을 시작한다.
- 이렇게 진행하면 '최대'지점에서 좌우 포인터가 만나게 된다. 이 때 반복이 중지된다.
🤨❓ 그렇다면 왜 왼쪽과 오른쪽을 나눠서 진행하며 최대 높이가 그 기준이 될까?
그 이유는 왼쪽과 오른쪽 중 최대 높이가 낮거나 같은 곳의 물은 분명히 고이기 때문이다.
그렇기 때문에 최대 높이가 낮은 쪽은 자신의 최대 높이보다 더 높아질때까지 고인물을 계산할 수 있다.
또한, 다른쪽의 최대 높이가 더 높아지면 낮은쪽에서 높은쪽으로 다시 최대 높이를 계산하면 된다.
이렇게 진행하다보면 두 포인터는 한 곳에서 만나게 된다.
투 포인터를 통해 O(n) 만에 해결이 가능하다.
-
스택 쌓기
벽의 높이를 스택에 쌓아나가면서 변곡점을 만날 때마다 고인 물의 양을 계산한다.
현재 높이가 바로 이전의 최근 높이보다 높을 때가 바로변곡점이다.
현재 바로전에 스택에 쌓인 높이는 바닥 높이가 되고 그 이전에 쌓여있는 원소의 인덱스는 고인물의 가로 길이를 구하는 인덱스가 된다. 이 가로 길이를 구하는 원소의 높이와 현재 높이 중 더 낮은 것이 고인물을 담을 수 있는 최대 높이가 된다.따라서, 고인물의 양은 담을 수 있는
(최대 높이 * 가로 길이)가 된다.
🛠 코드
- 리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.
- 투 포인터 풀이
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
rain = 0
while left <= right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if left_max <= right_max:
rain += left_max - height[left]
left += 1
else:
rain += right_max - height[right]
right -= 1
return rain- 스택 쌓기
class Solution:
def trap(self, height: List[int]) -> int:
stack = []
volume = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
bottom_height_idx = stack.pop()
if not stack:
break
distance = i - stack[-1] - 1
height_diff = min(height[i], height[stack[-1]]) - height[bottom_height_idx]
volume += distance * height_diff
stack.append(i)
return volume📝 정리
- 스택 방식은 이해하기가 너무 어렵다..
🎈 참고
Go Go