[ LeetCode - 11 ] Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/

Container With Most Water - LeetCode

 

먼저 첫 접근은 Brute-Force 방식으로 접근했다. 역시 기본 방법이 최고지

... 하지만 시간 초과로 다른 방법을 생각할 수 밖에 없었는데 loop 한 번으로 끝낼 수 있는 방법은 Two-Pointer 알고리즘밖에 떠오르지 않았는데 다행히도 통과 했다.

---

[ 📌 풀이 ]

양쪽 끝을 각 각의 포인터로 잡고 좁혀가면서 넓이를 구하는 로직이다.

 

1. 양쪽 포인터(인덱스)에 해당하는 높이(height) 중에서 작은 height를 찾아서 포인터 사이의 거리를 구해서 곱해서 큰 값 갱신한다.

2. 높이가 더 낮은 쪽을 좁혀준다. (if 조건문)

---

[ 📌 코드 - Python (Failed) ]

class Solution:
    def maxArea(self, height: list[int]) -> int:
        Len, ans = len(height), 0
        
        for i in range(Len):
            for j in range(i + 1, Len):
                min_height = min(height[i], height[j])
                ans = max(ans, min_height * (j - i))

        return ans

 

[ 📌 코드 - Python (Solved) ]

class Solution:
    def maxArea(self, height: list[int]) -> int:
        ans, left, right = 0, 0, len(height) - 1

        while left < right:
            ans = max(ans, min(height[left], height[right]) * (right - left))

            if height[left] > height[right]:
                right -= 1
            else:
                left += 1

        return ans

---

[ 📌 결과 ]

[ Result ]