[알고리즘] LeetCode Medium - Container With Most Water

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

10 / 50

 

탐색

12 / 50

 

기초 동적 프로그래밍

10 / 50

---

투포인터

3 / 10(NEW!)

 

이분탐색

0 / 10

---

문제

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=leetcode-75 

Container With Most Water - LeetCode

→ LeetCode 75 / Medium 문제

---

문제 해결 아이디어

투 포인터 알고리즘 문제

1. start를 첫번째 인덱스, end를 마지막 인덱스로 둔다.
2. start ~ end를 구간으로 할 때 얻을 수 있는 max_container를 구한다.
3. height[start]가 height[end]보다 작으면 start를 늘이고, 그 외에는 end를 줄인다.
4. 2 ~ 3 과정을 반복한다.

---

구현

내 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        answer = 0
        start = 0
        end = len(height) - 1
        while start < end:
            min_height = min(height[start], height[end])
            answer = max(answer, min_height * (end - start))
            if height[start] < height[end]:
                start += 1
            else:
                end -= 1
                
        return answer

---

메모

---

마치며

오..오랜만입니다