[Leetcode] 11. Container With Most Water (Python 풀이)

막대들의 높이가 리스트로 주어질 때, 두 막대 사이의 최대 넓이를 가지게 하는 "넓이"를 구하자. 이상적인 최대 넓이는 두 막대가 가장 멀리 떨어져있으면서, 높이가 최대가 되게 하는 것이다.

 

가장 큰 넓이와 높이를 유지하게 하는 탐색을 투 포인터로 손쉽게 해결할 수 있는데.. 처음에 제일 양쪽 끝에서 시작하면서, 둘 중의 낮은 막대를 점점 안쪽으로 옮겨오면서 넓이를 계산하는거다. 이걸 두 막대의 포인터가 교차하는 지점까지 탐색을 한다.

 

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

        st = 0
        ed = len(height)-1

        while st <= ed:
            answer = max(answer, (ed-st)*min(height[st], height[ed]))

            if height[st] < height[ed]:
                st += 1
            else:
                ed -= 1

        return answer

 

아이디어는 굉장히 단순한데, 코드도 굉장히 단순하다.

 

while문 안쪽의 첫번째 라인이, 최대 넓이를 계속 갱신한다. 

 

그리고 막대의 높이를 기준으로 포인터를 계속 옮겨준다.