•
문제 설명 : 주어진 높이 배열에서 두 라인을 선택하여 가장 많은 물을 담을 수 있는 컨테이너의 최대 용량을 구하여 반환
•
풀이 방법
◦
투포인터로 양쪽을 순회하는 것까지는 생각했지만, 모든 기둥을 순회한다면 O(N^2) 이기 때문에 좋은 풀이는 아니라고 생각했다.
◦
실제 물 높이를 결정하는 것은 양 기둥 중 낮은 높이의 기둥이기 때문에, 낮은 기둥이었던 포인터를 옮겨 더 높은 기둥을 찾는 방식을 택하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_water_amount = 0
while left < right:
new_water_amount = min(height[left], height[right]) * (right - left)
max_water_amount = max(max_water_amount, new_water_amount)
# 기준이 되는 기둥을 변경해줘야한다
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water_amount
Python
복사