[LeetCode] Container With Most Water

문제 링크 >> https://leetcode.com/problems/container-with-most-water/

 

 

📋 문제

You are given an integer array height of length n.

There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

 

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

 

Notice that you may not slant the container.

 

👉 입출력

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

 

 

📝 풀이

❌ 첫 번째 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        result = 0
        for i in range(len(height)):
            for j in range(i+1, len(height)):
                w = j-i
                h = min(height[i], height[j])
                result = max(result, w*h)
        return result

 

브루트포스 방식으로 풀려고 했더니 시간초과가 난다.

 

✔️ 두 번째 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        result = 0
        start, end = 0, len(height)-1

        while start < end:
            w = end - start
            h = min(height[start], height[end])
            result = max(result, w*h)

            if height[start] < height[end]:
                start += 1
            else:
                end -= 1

        return result

 

문제 분류에 투 포인터라는 힌트가 있는 것을 보고 투 포인터로 풀어봤다.

 

result는 정답인 넓이를 담을 변수이고 start와 end는 height의 인덱스를 조정할 포인터이다.

start는 0, end는 height의 마지막 인덱스 번호로 초기화한다.

 

start가 end보다 작은 경우, 그러니까 리스트를 순회할 수 있을 때에 대해 while문을 돌린다.

그리고 만들 수 있는 container의 넓이를 구해 result에 저장한다.

이때 result는 이전 결과와 비교해 최대값을 저장한다.

 

탈출 조건을 충족하기 위해 start와 end를 조정해 다른 요소들을 살펴볼 수 있도록 한다.

만약 height[start]의 값이 height[end]보다 작다면 start를 조정하고 크거나 같다면 end를 조정한다.

 

✔️ 세 번째 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        result = 0
        start, end = 0, len(height)-1

        while start < end:
            if height[start] < height[end]:
                area = height[start] * (end-start)
                start += 1
            else:
                area = height[end] * (end-start)
                end -= 1
            result = max(result, area)

        return result

 

두 번째 풀이를 개선한 코드이다.

어차피 if문에서 start와 end가 가리키는 height 요소의 값을 비교하고 있기 때문에 각 상황에 대해 if문 안에서 넓이를 구하고 start와 end의 값까지 조정하는 것이다.

 

두 번째 풀이의 경우 런타임이 1050ms인 반면 세 번째 풀이는 764ms이다.