leetcode algorithm study python

파이썬 알고리즘 : Container With Most Water

이진탐색

2024년 5월 23일 알고리즘 문제풀이

문제

난이도

medium

코드

1차시도

시간초과(50/62) 모두 탐색했는데 시간초과가 떴다.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def check(self,a,b,height):
        val = min(height[a], height[b])
        return abs(b-a)*val

    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        for a in range(n-1):
            for b in range(a+1,n):
               ans = max(ans, self.check(a,b,height))
        return ans

2차시도

메모리초과(49/62) 인덱스 중 2개를 골라 처리하려 했는데 2개의 숫자 조합을 만들기 위한 배열이 메모리초과가 떴다. 아무래도 접근 방법 자체가 틀린것같다.

1
2
3
4
5
6
7
8
9
10
11
12

from itertools import combinations

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        tmp = [i for i in range(len(height))]
        arr = list(combinations(tmp,2))
        for case in arr:
            w = abs(case[0]-case[1])
            h = min(height[case[0]], height[case[1]])
            ans = max(ans, w*h)
        return ans

3차시도

성공(62/62) 혹시나 싶어 index로 이진탐색했더니 됐다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from itertools import combinations

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        left = 0
        right = len(height)-1
        while left < right:
            mid = (left+right)//2
            w = right-left
            h = min(height[left],height[right])
            ans = max(ans, w*h)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans
CATALOG
    algorithm