[Algorithm] LeetCode - Container With Most Water

📠 문제

• Container With Most Water
• 난이도: Medium
• 주어진 배열에서 양 끝점으로 한 가장 큰 직사각형의 넓이를 구하는 문제

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

💡 풀이

첫 번째로 가장 무식하게 모든 경우의 수를 체크하는 방법이 있다. 물론 n의 입력값이 10^5이기 때문에 시간초과!

func maxArea(_ height: [Int]) -> Int {
    let count = height.count
    var result = 0
    
    for start in 0..<count {
        for end in (start..<count) {
            let area = (end - start) * min(height[start], height[end])
            result = max(result, area)
        }
    }

    return result
}

어떻게 효율적으로 접근할 수 있을까? 🤩 이 문제가 정말 재밌었던 게 조금만 생각해 보면 쉬운 방법이 나온다. 조건 하나만 추가해 주면 문제가 풀린다.

바로바로 아래의 조건 한줄을 루프에 추가해 주면 된다. 그 이유는 만약에 양끝에서 시작해서 height[start]가 height[end]보다 적다면 종료해 주면 된다. 그때가 바로 최대일 수밖에 없다. start의 높이는 고정이 되어있기 때문에 height[start]의 높이를 사용해서 넓이를 쟀을 때가 최대이다.

if height[start] < height[end] { break }

최종 코드는 아래와 같다.

func maxArea(_ height: [Int]) -> Int {
    let count = height.count
    var result = 0
    
    for start in 0..<count {
        for end in (start..<count).reversed() {
            let area = (end - start) * min(height[start], height[end])
            result = max(result, area)
            if height[start] < height[end] { break }
        }
    }

    return result
}

🔨 풀이 개선

하지만 아쉬웠던 건 92ms로 풀긴 했지만 Beats 5.19%... 그리고 위의 풀이는 결국 O(n^2)의 시간복잡도이다. 결국 이것보다 훨씬 효율적인 방법이 있다는 뜻이다. 바로바로 투포인터 알고리즘! left, right부터 시작해서 높이가 더 높은곳으로 나아가는 방식으로 코드를 작성하면 O(n)의 시간복잡도로 풀 수 있다.

func maxArea(_ height: [Int]) -> Int {
    var left = 0
    var right = height.count - 1
    var result = 0

    while left < right {
        let area = (right - left) * min(height[left], height[right])
        result = max(result, area)

        if height[left] < height[right] {
            left += 1
        } else {
            right -= 1
        }
    }

    return result
}

오케이... 3ms로 약 30배 빠르게 개선했다. 하지만 내앞에 계신 60%분들도 제치고 싶다...!

O(n)보다 개선하는 것은 조건을 추가해주지 않는 이상 불가능하다. 우선 불필요한 연산을 줄이고자 max함수를 쓰지 않고 아래와 같이 코드를 작성했더니 바로 개선이 되었다.

func maxArea(_ height: [Int]) -> Int {
    var left = 0
    var right = height.count - 1
    var result = 0

    while left < right {
        let area = (right - left) * min(height[left], height[right])
        if area > result { result = area } // max 함수를 쓰지 않음

        if height[left] < height[right] {
            left += 1
        } else {
            right -= 1
        }
    }

    return result
}

0ms... 굳...👍 계산상 ♾️배 개선했다.