⭐️ LeetCode 알고리즘 풀이 (with Python)

# Container With Most Water

[Quetion]

LeetCode 11. Container With Most Water

📌 접근법

[문제 이해]

• 배열의 길이를 x축, 배열의 값을 기둥의 높이라고 한다.
• 두 기둥 사이에 물을 담을 수 있다고 할 때, 물을 담을 수 있는 최대 용량 구하기

두 기둥을 가리킬 수 있는 포인터 2개가 필요하므로 투 포인터 접근법을 생각했다.
그래서 생각한 코드의 흐름은 다음과 같다.

• 배열의 가장 첫번째 값과 마지막 값을 가리키는 포인터 2개 생성
• 두 포인터가 가리키는 값 중 작은 값을 고른다.
• 물의 양 = 고른 값 * 두 기둥 사이의 거리
• 작은 값을 가진 포인터를 왼쪽 혹은 오른쪽으로 1칸씩 이동

💻 구현

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l,r = 0,len(height)-1
        # 물의 양
        amount = 0
        while l != r:
        	# 두 포인터가 가리키는 값 중 더 작은 값
            x = min(height[l], height[r])
            
            # 계산한 물의 양이 기존 보다 크면 갱신
            amount = max(amount, (x * (r-l)))
            
            # 더 작은 값을 가리키는 포인터를 이동
            if height[l] <= height[r]:
                l+=1
            else:
                r-=1
        return amount

Runtime: 594ms | Memory: 29.1MB
LeetCode 코드 중 Runtime 69%, Memory 96% 해당하는 결과

📌 로직 핵심

• 두 기둥 중 짧은 기둥만큼 물을 채울 수 있으므로 x 변수에 더 짧은 기둥의 높이를 담았다.
• 그리고 x와 두 기둥 사이의 거리인 r-l을 곱하여 물의 양을 구하고, 기존에 계산된 물의 양보다 크면 갱신한다.
• 다음 기둥으로 이동하면서 물을 더 많이 채울 수 도 있기 때문에 더 짧은 기둥을 다른 기둥으로 교체한다.

📝 Container With Most Water 회고

• 해당 코드의 시간복잡도는 O(N), 공간 복잡도는 O(1)이다.

• 코드를 제출하고 다른 대부분의 솔루션들도 max(), min() 함수를 활용하여 투포인터 접근 법으로 문제를 해결한 것을 확인했다.

• abs() 함수로 두 기둥간의 거리를 얻는 코드도 있었다. 똑같은 생각을 했었지만 오른쪽 포인터가 무조건 더 크기때문에 (오른쪽 - 왼쪽)으로 해결할 수 있어서 abs() 활용은 필요하지 않다고 판단했다.

• x변수에 할당한 것을 amount 연산 과정에 합치는 것으로 코드를 더 간결하게 개선할 수 있지만, 코드의 가로 길이가 그만큼 길어지기 때문에 가독성을 낮춘다고 생각하여 따로 개선을 진행하지는 않았다.