LeetCode [11]: Container With Most Water

📌 LeetCode [11]: Container With Most Water

🔗 문제 링크

---

문제 설명 📄

길이가 ( n )인 정수 배열 height가 주어질 때, 두 막대를 선택하여 담을 수 있는 물의 최대량을 구하는 문제입니다.
물의 양은 다음과 같이 계산됩니다:

• 물의 양 = ( 너비 × 낮은 막대의 높이 )
• 두 막대의 위치에 따른 너비는 두 막대의 인덱스 차이로 계산됩니다.

예:

• height = [1,8,6,2,5,4,8,3,7]
• 최대 물의 양은 49이며, 이는 막대 height[1]과 height[8]에서 나옵니다.

---

문제 접근 방식 📋

1. 두 포인터 사용:
   • left와 right 포인터를 배열의 양 끝에 위치.
   • 각 포인터는 배열의 양 끝에서부터 중앙으로 이동하며 최대 물의 양을 계산.
2. 물의 양 계산:
   • 현재 너비 = right - left
   • 현재 물의 양 = 너비 × min(height[left], height[right])
   • 최대 물의 양을 갱신.
3. 포인터 이동 조건:
   • 더 낮은 높이의 막대를 이동:
     • 이유: 물의 양은 낮은 막대의 높이에 의해 제한되므로, 더 높은 막대를 유지하는 것이 유리.
4. 반복 종료:
   • left와 right 포인터가 교차하면 종료.

---

Solution 💻

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

        while left < right:
            water = length * min(height[left], height[right])
            answer = max(answer, water) 


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

            length -= 1

        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(n))
  • 두 포인터가 배열을 한 번씩만 탐색합니다.
• 공간 복잡도: (O(1))
  • 추가 공간을 사용하지 않습니다.

---

리팩토링 🛠️

개선된 코드

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

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

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

        return answer

리팩토링 후 차이점

• 불필요한 length 변수를 제거하여 코드 간결화.
• 물의 양 계산을 반복문 내에서 직접 처리.

---