LeetCode알고리즘 Container With Most Water

오늘은 11번을 풀어보겠습니다. 
중간 난이도고 53.9%의 성공률을 보입니다.

ㄱㄱ

길이가 n인 height 정수 배열이 제공됩니다.
i번째 선의 두 점이 (i, 0) 그리고 (i, height[i])처럼 n개의 수직선이 그려집니다.
컨테이너에 가장 많은 물이 포함될 수 있는 x축인 두 개의 선을 찾으세요.
컨테이너가 저장할 수 있는 최대 물의 양을 리턴해야합니다.
컨테이너를 기울이는 건 안된다고 합니다.

주어진 예시를 보겠습니다.

[1,8,6,2,5,4,8,3,7] 9개의 높이를 받았고
인덱스에 맞게 높이를 그려주면 위 이미지와 같습니다.
컨테이너가 저장할 수 있는 최대 물의 양을 리턴해야 하니 컨테이너가 클수록 좋습니다.
해당 예제에서는 1번째 인덱스 8 그리고 8번째 인덱스 7에서 직선을 만들었을 때가 가장 넓은 컨테이너가 되겠죠!
넓이 7 높이 7 (7 * 7 = 49)으로  49가 리턴되면 됩니다.

 

투 포인터를 사용해서 풀어보겠습니다.

func maxArea(_ height: [Int]) -> Int {
    guard height.count > 1 else { return -1 }
    
    var left = 0
    var right = height.count - 1
    var answer = 0
    
    while left < right {
        let minHeight = min(height[left], height[right])
        let current = minHeight * (right - left)
        answer = max(answer, current)
        
        if height[left] < height[right] {
            left = left + 1
        } else {
            right = right - 1
        }
    }
    
    return answer 
}

적어도 두 개의 높이가 주어져야 컨테이너를 형성할 수 있기 때문에 guard로 height.count > 1의 제약을 걸어두었습니다.
(없어도 상관없음)

left, right변수를 선언해 가장 끝 인덱스 값을 할당해줍니다.
answer은 정답을 위한 변수입니다.

while문을 통해 left < right 제약을 둡니다. 
높이가 작은 쪽이 컨테이너의 높이가 되기 때문에 height[left], height[right]를 비교해 작은 값을 minHeight에 넣어줍니다.
현재 컨테이너의 넓이를 구해줍니다. (컨테이너의 넓이 = 가로 * 세로)
컨테이너가 저장할 수 있는 최대 물의 양을 구해야 하기 때문에 max로 현재 answer에 든 값과 current 현재 컨테이너의 넓이를 비교해 더 큰 값을 answer에 저장해줍니다.

height[left]와 height[right]를 비교해 height[left]이 더 작으면 왼쪽 인덱스를 1 증가시켜주고
height[right]가 더 작으면 오른쪽 인덱스를 1 감소시켜줍니다. 
즉 left는 인덱스 0부터 시작하면서 오른쪽으로 움직이고
right는 인덱스 height.count - 1부터 시작하면서 왼쪽으로 움직여
즉 비교할 범위를 줄이는 방식입니다.
(two pointers algorithm)

이렇게 시간복잡도 O(n) 공간복잡도 O(1)로 문제를 해결할 수 있습니다.

이렇게 했을 때 결과는

나름 메모리 작게 사용했다고 생각했는데 ^^? 다른 사람들은 더 작게 사용했나봅니다.

 

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