Container With Most Water - leetcode

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

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var max = 0
        // 시작 인덱스
        var startIndex = 0
        // 끝 인덱스
        var endIndex = height.count - 1
        
        // 시작 인덱스가 끝 인덱스 보다 작을 때만 반복
        while (startIndex < endIndex) {
            // x축 길이 구하고
            let x = abs(startIndex - endIndex)
            // y축 길이는 두 막대 중 길이가 작은 걸로
            let y = min(height[startIndex], height[endIndex])
            
            // 가장 큰 넓이를 max에 저장
            max = max < x * y ? x * y : max

            // 두 막대 중 작은 막대 쪽을 좁히기
            if height[startIndex] < height[endIndex] {
                startIndex += 1
            } else {
                endIndex -= 1
            }
        }
        return max
    }
}

배열이 주어지면 가장 많은 물을 담을 수 있는 면적을 구하는 문제.

 

처음에는 브루트포스로 이중 반복문을 사용했는데 당연히 시간초과가 뜸.

다시 생각해보다가 젤 큰 범위를 잡아서 점점 좁혀 나가도 되나? 하는 아이디어가 떠오름.

 

왜냐하면 두 막대 중 높은 막대 쪽을 좁히면 무조건 이전 값보다 작아지기 때문.

예를 들어 위 그림에 경우엔 1 ~ 7이 젤 큰 범위인데 이때 담을 수 있는 물의 면적은 6임. ( (6 - 1) * 1 ) 이때 높은 쪽을 좁히면 높이는 똑같은데 너비가 1 줄어듬.

 

따라서 높은 쪽은 볼 필요가 없고 낮은 쪽을 좁혀나가야함. (현재 상황에서 최선의 선택을 하는 그리디 알고리즘 !?)