[leetcode] Container With Most Water (swift)

문제 

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

Container With Most Water - LeetCode

문제 요약

아래 그림과 같이 Container가 있고 물을 최대한 많이 담을 수 있는 넓이를 찾는 문제입니다. 아래 예시같은 경우 높이 7, 너비 7을 가진 49 크기의 container가 최대 사이즈입니다. 

 

풀이

역시나 O(N^2)의 풀이법은 바로 떠오릅니다. 막대 하나를 기준으로 잡고 나머지 막대 하나 정하는 것을 나머지 막대들을 전부 순회하며 넓이가 최대인 상황을 구합니다. 여기서 주의할 점은 중간에 위치한 막대를 기준을 잡을 때, 이미 구한 container의 크기가 최대인지 확인해야 시간초과가 나지 않습니다. 문제에서 최악의 경우 10^5 만큼의 막대들이 있게 되기 때문에 시간복잡도 O(N^2)라고 생각하면 굉장히 느린 시간입니다. 

풀이코드 1

Runtime 828ms | Memory 18.3MB

이 문제도 O(N)의 시간복잡도로 해결하는 방법이 역시나 있습니다. 넓이가 최대가 되기위해서는 높이와 너비가 최대여야 합니다. 하지만 높이는 우리가 알 수 있는 것이 아니지만, 너비는 첫번째 막대와 마지막 막대를 선택해야 최대가 되는 것을 알 수 있습니다. 처음과 끝에 포인터 left, right를 두고 만약 처음 막대가 마지막 막대보다 높이가 작다면 left에 1을 더하고, 마지막 막대가 처음 막대보다 높이가 작다면 right에 1을 빼는 방식으로 진행합니다. 너비가 줄어들지만 높이는 계속 최댓값이라는 것이 보장되기 때문에 마지막에 구한 넓이가 최대라는 점은 보장합니다.

풀이코드 2

Runtime 598ms | Memory 18.2MB