[Leetcode] 11. Container With Most Water_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '11. Container With Most Water'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Container With Most Water' 알고리즘 문제

 

STEP 2. 'Container With Most Water' 코드(code)

 

STEP 3. 'Container With Most Water' 해설

 

STEP 4. 'Container With Most Water' solution

 

반응형

 

STEP 1. '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.

 

길이 n의 정수 배열 높이가 지정됩니다. x축과 함께 용기를 형성하여 용기에 물이 가장 많이 포함되도록 하는 두 개의 선을 찾습니다. 용기에 저장할 수 있는 최대 양의 물, 연산을 구합니다.

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

---

STEP 2. 'Container With Most Water' 코드(code)

 

■ Runtime: N/A
■ Memory Usage: N/A 

 

접근 방식은 height에서 내림차순으로 정렬한 list를 새롭게 만들어서, 가장 큰 height를 하나씩 제거하면서 연산을 진행했습니다. 다만, 이중 반복문을 활용해서 while - for을 통해 연산 속도가 너무 느려서 "Time Limit Exceeded"가 나왔습니다.

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        number_lst = sorted(height, reverse = True)
        check_prev = 0
        width_lst = []
        
        while len(number_lst) != 0 :
            max_height = max(number_lst)
            
            # check max_height
            for i in range(len(height)):
                if height[i] == max_height:
                    width_lst.append(i)
                    
            while max_height in number_lst:
                number_lst.remove(max_height)
                    
            width = max(width_lst) - min(width_lst)
            tall = max_height
            check = width * tall
           
            answer = check_prev if check_prev > check else check
            check_prev = answer
        
        return answer

---

그래서 이를 개선하기 위해, Two pointer python solution을 활용한 코드를 확인했습니다.

 

■ Runtime: 1544 ms, faster than 5.17% of Python3 online submissions for Container With Most Water.
■ Memory Usage: 27.2 MB, less than 95.20% of Python3 online submissions for Container With Most Water.

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height) -1
        width = len(height) -1
        maxi = 0
        while l < r:
            area = min(height[l], height[r]) * width
            maxi = max(maxi, area)
            if height[l] < height[r]:
                l+=1
            else:
                r-=1
            width -=1
        return maxi

---

STEP 3. 'Container With Most Water' 해설

 

위에 작성된 코드의 주석을 아래처럼 달아봤습니다.

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        '''
        알고리즘 접근 방식은 처음부터 진행되는 순방향과 마지막부터 진행되는 역방향, 2개를 활용해서
        연산을 통해 가장 높은 넓이를 구하는 것입니다.
        
        '''
        l = 0 # 순방향 시작점
        r = len(height) - 1 # 역방향 시작점
        width = len(height) -1 # 초기 가로값
        maxi = 0 # 초기 넓이값
        
        while l < r:
            area = min(height[l], height[r]) * width # 넓이
            maxi = max(maxi, area) # 두 값 중에서 
            
            # 순방향과 역방향을 비교하여, 작은 쪽이 한 칸씩 이동하는 방향
            if height[l] < height[r]: 
                l += 1
            else:
                r -= 1
                
        return maxi

 

 

STEP 4. 'Container With Most Water' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다. 

 

■ Runtime: 752 ms, faster than 91.90% of Python3 online submissions for Container With Most Water.
■ Memory Usage: 27.4 MB, less than 89.24% of Python3 online submissions for Container With Most Water.

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        water = 0
        head = 0
        tail = len(height) - 1

        for cnt in range(len(height)):

            width = abs(head - tail)

            if height[head] < height[tail]:   
                res = width * height[head]
                head += 1
            else:
                res = width * height[tail]
                tail -= 1

            if res > water:
                water = res

        return water

 

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '11. Container With Most Water'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.