Container With Most Water - LeetCode
벽이 될 수 있는 막대 그래프와 같은 모양이 주어질 때, 가장 물을 많이 채울 수 있는 경우를 찾는 문제다.
고려했던 사항은 다음과 같다.
풀이 과정은 다음과 같다.
leetcode를 풀면 느끼는 거지만 Medium이 상당히 어렵게 느껴질 때가 있다. 이 문제도 코드는 간단하게 나왔지만 오랜 시간 고민하여 얻고, 얻고나서도 허탈했다. 다른 답안들을 보니 dp, two pointer이렇게 두가지 경우의 답안이 있는것 같았다. dp의 경우는 너무 어려워보여서 pass하고, two pointer의 경우는 나와 비슷하지만 좀더 최적화되어 있는것 같았다.(무조건 지금보다 높은 벽을 만날 때까지 모은다.) 여기서, two pointer는 정렬된 데이터를 이용할 때 좋다고 공부하였는데 아닌 경우에도 사용될 수 있는걸 깨달았다.
class Solution:
def maxArea(self, height: List[int]) -> int:
answer = 0
l, r = 0, len(height) - 1
while l < r:
answer = max(answer, min(height[l], height[r]) * abs(l - r))
if height[l] < height[r]:
l += 1
else:
r -= 1
return answer