[알고리즘] Container With Most Water

Leetcode의 Container With Most Water 문제를 풀어보도록 하겠습니다.

문제

물의 높이를 나타내는 양의 정수로 이뤄진 배열이 주어졌을 때, 두개의 높이로 만들 수 있는 수조의 최대 넓이를 구하라.
단, 배열은 최소 2개의 원소로 구성되어 있고 수조를 기울일 수 없다.

예제

  • 입력: [1,8,6,2,5,4,8,3,7]
  • 출력: 49

2번째 높이 8과 마지막 높이 7을 가지고 넓이 49짜리 수조를 만들 수 있습니다.
이 수조의 높이 87 중 작은 값인 7이며, 너비는 두 값의 거리인 7(index 8 - index 1)이기 때문입니다.

풀이

배열에서 임의의 2개의 수를 가지고 만들 수 있는 수조의 넓이를 생각해보겠습니다.
일단 수조의 높이는 두 수 중 낮은 값에 의해서 결정이 됩니다. (수조를 기울일 수 없으므로…)
그리고 수조의 너비는 두 수의 거리에 의해서 결정됩니다.

이를 수식으로 나타내면 다음과 같습니다.

1
Area(a, b) = min(arr[a], arr[b]) *  (b - a)

즉, 이 문제는 배열로 부터 선택할 수 있는 모든 경우의 2개의 수에 위 수식을 대입하여 최대 넓이를 찾을 수 있습니다.
하지만 이러한 접근 방법은 nP2 = O(N^2) 시간이 소요되는데 Leet Code에서는 Time Limit Exceeded 때문에 통과가 되지 않습니다.

생각해보면 배열에서 첫 값과 마지막 값을 선택했을 때 최대 넓이가 될 확률은 중간에서 임의의 2개의 값을 선택했을 때 보다 높을 것 같습니다. (특히 배열이 길다면…)
배열의 가장자리의 값을 선택해 먼저 넓이를 구하고, 왼쪽을 한 칸 당기거나 오른쪽을 한 칸 당겨서 다시 넓이를 구하면서 넓이 값들을 비교해나갈 수 있습니다.
이 때 왼쪽과 오른쪽을 번갈아 가서 당기지 않고, 한쪽만 당길 수 있다면 O(N) 알고리즘으로 나아갈 수 있습니다.

두 개의 높이 중 높은 쪽을 줄이면 넓이는 무조건 전보다 작아지게 됩니다. 왜냐하면 수조의 높이는 두 수 중에 낮은 값이 결정이 되고 너비는 무조건 1이 줄이들기 때문입니다.
하지만 두 개의 높이 중 낮은 쪽을 줄이면 줄어든 너비를 상쇄할만큼의 높이 상승을 기대할 수 있습니다.
이렇게 낮은 쪽을 계속 줄여나가다보면 한 점에서 만나게 될 것이고, 이 때 여태까지 나온 값 중 가장 큰 값이 우리가 찾는 가장 큰 넓이가 됩니다.

구현

두 개의 포인터에 배열의 첫 인덱스와 마지막 인덱스를 저장하고 시작합니다.
너비를 줄일 때 마다 넓이를 계산해서 여태까지 나온 최대 넓이와 비교합니다.

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxArea(self, height):
max_area = 0
low, high = 0, len(height) - 1
while low < high:
area = min(height[low], height[high]) * (high - low)
max_area = max(area, max_area)
if height[low] < height[high]:
low += 1
else:
high -= 1
return max_area

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
int low = 0, high = height.length - 1;
while (low < high) {
int area = Math.min(height[low], height[high]) * (high - low);
maxArea = Math.max(area, maxArea);
if (height[low] < height[high]) low++;
else high--;
}
return maxArea;
}
}

복잡도

N을 배열의 길이라고 했을 때, 위 코드의 복잡도는 다음과 같습니다.

  • 시간: O(N)
  • 공간: O(1)

하나의 while 루프를 사용하여 너비를 계속 줄여나기기 떄문에, 소요되는 시간은 배열의 길이에 비례합니다.
최대 넓이를 저장하기 위한 하나의 변수와 두 개의 포인터만을 사용하므로 필요한 공간은 배열의 길이와 무방하게 일정합니다.

문제 출처

공유하기