[LeetCode] 11번 - Container With Most Water [Swift]

문제 링크

Container With Most Water - LeetCode

문제

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

 

Example 1:

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.

Example 2:

Input: height = [1,1] Output: 1

Example 3:

Input: height = [4,3,2,1,4] Output: 16

Example 4:

Input: height = [1,2,1] Output: 2

 

Constraints:

• n == height.length
• 2 <= n <= 3 * 10^4
• 0 <= height[i] <= 3 * 10^4

 

문제 풀이

이 문제는 문제의 그림에 나온 대로 주어진 배열로 만들 수 있는 가장 큰 컨테이너를 만드는 문제입니다.

우선 이 문제를 가장 쉽게 풀 수 있는 방법은 역시나 모두 해보는 것인데 이 경우 시간 복잡도가 O(n^2)가 나오게 되며 직접 해 본 결과 시간 초과를 발생합니다.

따라서 다른 방법을 생각해야 하는데, 저는 two pointer 개념을 사용해서 풀었습니다.

시작할 때 배열의 시작과 끝을 가리키는 두 개의 포인터를 만듭니다.

하나는 left, 하나는 right라고 이름을 짓고 left의 값이 더 작으면 left + 1을 해주고 right의 값이 더 작으면 right - 1을 해주다 left가 right보다 커지는 순간에 반복을 끝내면 됩니다.

매 반복마다 그 순간의 left, right로 컨테이너를 만들어보고 만약 기존의 값보다 크면 값을 변경해주면 됩니다.

 

즉 아래와 같이 반복하면 됩니다.

 

1. left, right로 컨테이너를 만들고 기존 값보다 크면 값을 변경.

2. left, right를 비교하여 left가 더 작으면 left + 1, right가 더 작으면 right - 1을 해준다.

 

이렇게 푸니까 시간 초과 없이 문제를 풀 수 있었습니다!

소스 코드

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var result: Int = 0
        var left: Int = 0
        var right: Int = height.count - 1
        
        while left < right {
            let now = min(height[left], height[right]) * (right - left)
            if result < now {
                result = now
            }
            if height[left] < height[right] {
                left += 1
            } else {
                right -= 1
            }
        }
        
        return result
    }
}