[LeetCode] Container With Most Water

https://leetcode.com/problems/container-with-most-water/submissions/

Container With Most Water - LeetCode

그래프 높이가 주어졌을 때 가장 넓이가 큰 경우를 구하는 문제이다.

이건 예시 그림을 보는게 이해가 빠르다. 

 

 

가장 큰 넓이를 가지는 경우는 위 경우( width = 7, height = 7)이다. 

 

문제를 풀어나가는 원리는 width를 가장 큰 범위부터 시작해서 줄여나가면서 넒이를 비교해주는 것이다. 

 

1. index를 먼저 정해준다. left = 0 , right = 전체 길이 - 1

2. 높이는 두 지점에서 최솟값이 된다. 

3. 넓이를 구하고 최대인지 확인해준다. 

4. 확인 이후 다음 케이스로 넘어가기 위해 더 짧은 막대인 index를 한 칸씩 좁힌다. 

    4-1. left 값 < right 값 일 경우 left += 1, 반대일 경우 right -= 1

 

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        // 인덱스 설정
        var l = 0, r = height.count - 1
        var res = 0
        
        // 만나기 직전까지
        while l < r {
            // 넓이
            let temp = (r - l) * min(height[l],height[r]) 
            
            // 최대인 경우에만 할당
            if res < temp {
                res = temp
            }
            
            // 왼쪽 높이가 더 작다면 왼쪽 인덱스 +- 1 해서 범위를 점점 좁혀나간다. 
            if height[l] < height [r] {
                l += 1
            } else {
                // 반대의 경우 right -= 1을 하여 범위를 좁힌다. 
                r -= 1 
            }
        }
        
        return res
    }
}

 

Medium치고는 쉬운 문제..!

최대의 범위부터 줄여나가면서 면적을 구하는 Greedy한 문제. left/right 인덱스를 사용한 것을 보면 Two Pointers에 가까운 문제인 것 같기도 하다.