[Leetcode 아주 상세한 문제풀이] 11. Container with most water - 코드 line별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 11번 문제 Container with most water 다.

우선 문제를 살펴보자.

 

리트코드 11번 문제 Container with most water (링크)

Container With Most Water - LeetCode

Container With Most Water - LeetCode

 

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:
Input: height = [1,1]
Output: 1

 

 

문제 설명

문제를 살펴보면 우선 정수로 이루어진 배열이 주어지고, 이 배열은 해당 인덱스에서의 벽 높이를 나타낸다. 아래 그림에서 보는 것처럼 가로 축은 해당 인덱스, 세로 축은 해당 인덱스에 할당된 숫자를 의미한다.

이때 1번 벽과 8번 벽 사이에 물을 채우면 총 49칸의 물을 채울 수 있다. 8번 벽 보다는 6번 벽이 더 높아 1번과 6번 벽을 선택하는 것이 정답처럼 보이지만 우리는 물을 가장 많이 담을 수 있는 두 개의 벽을 선택해야 하기 때문에 가로 축이 더 긴 8번 벽을 선택하는 것이 정답이다.

 

 

문제 풀이

코드를 살펴보자.

우선 배열을 입력받을 함수를 정의해 준다 (line 1)

그리고 left 포인터를 가장 왼쪽에, right 포인터를 가장 오른쪽에 배치한다 (line 2-3)

max_area는 0으로 초기화 시켜준다.

그리고 left 포인터가 right 포인터보다 왼쪽에 위치하는 동안 while loop를 돌린다 (line 6)

이때 area를 계산하기 위해서는 높이 (height, h)와 너비 (width, w)를 구해야 하는데

높이의 경우 포인터가 위치한 두 벽 중 낮은 것 (물이 넘치기 때문에)을 선택하고 (line 7)

너비의 경우 두 포인터 사이의 거리다 (line 8)

여기서 구한 높이와 너비를 이용하여 area를 구하고

이때 구한 area가 기존 구했던 max area와 비교해 업데이트 한다 (line 10)

여기서 핵심 중 하나는 left, right를 어떻게 움직이느냐인데

left, right 포인터가 위치한 벽 높이를 비교해

왼쪽 벽이 낮으면 left 포인터를 오른쪽으로 하나 옮기고 (line 12-13)

오른쪽 벽이 낮으면 right 포인터를 왼쪽으로 하나 옮긴다 (line 14-15)

그 이유는 우리는 max area를 구해야 하는 거기 때문에

더 높은 벽을 탐색해야 하기 때문이다. 

예를 들어 left 포인터가 있는 벽의 높이가 8이고

right 포인터가 있는 벽의 높이가 3이라고 한다면

3보다는 높은 벽의 높이가 있는지를 탐색해야

더 큰 max area을 찾을 수 있는 기회가 있는 것이다.

 

 

문제 풀이 코드

def maxArea(height):
    left = 0
    right = len(height) - 1
    max_area = 0
 
    while left < right:
        h = min(height[left], height[right])
        w = right - left
        area = h * w
        max_area = max(max_area, area)
 
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
 
    return max_area
 
# Example usage
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(maxArea(height))
 

 

 

관련 문제

리트코드 1번 문제 Two sum 문제풀이

리트코드 15번 문제 3Sum 문제풀이

리트코드 33번 문제 Search in rotated sorted array 문제풀이

리트코드 53번 문제 Maximum subarray 문제풀이

리트코드 121번 문제 Best time to buy and sell stock 문제풀이

리트코드 152번 문제 Maximum product subarray 문제풀이

리트코드 153번 문제 Find minimum in rotated sorted array 문제풀이

리트코드 217번 문제 Contains duplicate 문제풀이

리트코드 238번 문제 Product of array except self 문제풀이

 

11. Container with most water