Logo

Container With Most Water

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

문제

길이가 n인 정수 배열 height가 주어졌을 때, n개의 수직선이 그려져있으며 i 번째 선은 좌표 (i, 0)과 (i, height[i])를 이은 선으로 나타낸다.

최고로 많은 물을 담을 수 있는 수조(container)를 만들어 낼 수 있는 두 개의 수직선을 찾고 그 수조가 담고 있는 최대 물의 양을 반환하라.

단, 배열은 최소 2개의 원소로 구성되어 있고 수조를 기울일 수 없다.

예제

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

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

풀이 1

주어진 배열에서 임의의 높이 두 개를 가지고 만들 수 있는 수조의 넓이는 어떻게 될까요? 수조의 넓이는 수조의 너비와 수조의 높이를 곱하면 되죠?

일단 수조의 너비는 인덱스의 거리에 의해서 결정됩니다. 그리고 수조의 높이는 두 인덱스의 값 중 낮은 값에 의해서 결정이 됩니다. (수조를 기울일 수 없으므로…)

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

area(s, e) = (e - s) * min(height[s], height[e])

단순무식하게 배열로부터 선택할 수 있는 모든 경우의 2개의 수에 위 수식을 대입하여 최대 넓이를 찾을 수 있을 것입니다.

이 알고리즘을 코드로 구현해볼까요?

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        for s in range(len(height) - 1):
            for e in range(s + 1, len(height)):
                area = (e - s) * min(height[s], height[e])
                max_area = max(area, max_area)
        return max_area
class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        for (int s = 0; s < height.length - 1; s++) {
            for (int e = s + 1; e < height.length; e++) {
                int area = (e - s) * Math.min(height[s], height[e]);
                maxArea = Math.max(area, maxArea);
            }
        }
        return maxArea;
    }
}
function maxArea(height: number[]): number {
  let maxArea = 0;
  for (let s = 0; s < height.length - 1; s++) {
    for (let e = s + 1; e < height.length; e++) {
      const area = (e - s) * Math.min(height[s], height[e]);
      maxArea = Math.max(area, maxArea);
    }
  }
  return maxArea;
}
func maxArea(height []int) int {
	maxArea := 0
	for s := 0; s < len(height)-1; s++ {
		for e := s + 1; e < len(height); e++ {
			area := (e - s) * min(height[s], height[e])
			maxArea = max(area, maxArea)
		}
	}
	return maxArea
}
impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut max_area = 0;
        for s in 0..height.len() - 1 {
            for e in s + 1..height.len() {
                let area = (e - s) as i32 * height[s].min(height[e]);
                max_area = area.max(max_area);
            }
        }
        max_area
    }
}

이 알고리즘을 LeetCode에 제출해보면 Time Limit Exceeded 오류가 나면서 통과가 되지 않을 것입니다. 왜 그럴까요?

이 풀이에서는 n개의 원소에서 2개를 나열하는 순열(permutation)을 수행하므로 시간 복잡도는 nP2, 즉, 빅오 표현법으로 O(n^2)이 됩니다. 따라서 여기서 우리는 O(n^2) 보다는 더 성능이 좋은 알고리즘을 구해야 한다는 것을 알 수 있습니다.

반면에 최대 넓이를 저장하기 위한 하나의 변수와 두 개의 포인터만을 사용하므로 필요한 메모리는 배열의 길이와 무관하게 일정합니다 공간 복잡도는 O(1)이 되겠습니다.

풀이 2

만약에 주어진 배열 내의 모든 수직선의 높이가 동일했더라면 당연히 최대 너비를 얻기 위해서 양쪽 가장자리의 수직선을 선택했겠죠?

이 점에 착안해서 이 문제는 두 개의 포인터로 풀 수 있습니다. 기본 아이디어는 수조를 배열의 양쪽 가장자리에서 시작해서 점점 너비를 좁혀나가는 건데요. 매번 시작 포인터를 오른쪽으로 한 칸 당기거나 종료 포인터를 왼쪽으로 오른쪽을 한 칸 당긴다면 O(n)의 시간 복잡도를 달성할 수 있을 것입니다.

여기서 중요한 문제는 과연 두 개의 포인터 중 어떤 포인터를 이동시키느냐겠죠? 두 개의 높이 중 높은 쪽을 줄이면 넓이는 무조건 전보다 작아지게 됩니다. 왜냐하면 수조의 높이는 두 수 중에 낮은 값이 결정이 되고 너비는 무조건 1이 줄어들기 때문입니다.

반면에 두 개의 높이 중 낮은 쪽을 줄이면 줄어든 너비 1을 상쇄할 만큼의 높이 상승을 기대할 수 있습니다. 이렇게 낮은 쪽을 계속 줄여나가다보면 한 점에서 만나게 될 것이고, 이때 여태까지 나온 값 중 가장 큰 넓이를 반환하면 됩니다.

문제에서 주어진 예제에 이 알고리즘을 적용해볼까요? 두 개의 포인터에 배열의 첫 인덱스와 마지막 인덱스를 저장해놓고 시작하겠습니다. 너비를 줄일 때마다 새로운 넓이를 계산해서 여태까지 나온 최대 넓이와 비교합니다.

 s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
                         e
area = (8 - 0) * min(1, 7) = 8 * 1 = 8
max_area = 0 < 8 = 8
    s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
                         e
area = (8 - 1) * min(8, 7) = 7 * 7 = 49
max_area = 8 < 49 = 49
    s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
                      e
area = (7 - 1) * min(8, 3) = 6 * 3 = 18
max_area = 49 > 18 = 49
    s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
                   e
area = (6 - 1) * min(8, 8) = 5 * 8 = 40
max_area = 49 > 40 = 49
    s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
                e
area = (5 - 1) * min(8, 4) = 4 * 4 = 16
max_area = 49 > 16 = 49
    s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
             e
area = (4 - 1) * min(8, 5) = 3 * 5 = 15
max_area = 49 > 15 = 49
    s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
          e
area = (3 - 1) * min(8, 2) = 2 * 2 = 4
max_area = 49 > 4 = 49
    s
[1, 8, 6, 2, 5, 4, 8, 3, 7]
       e
area = (2 - 1) * min(8, 6) = 1 * 6 = 6
max_area = 49 > 6 = 49

그럼 이 과정을 그대로 코드로 구현해볼게요?

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        s, e = 0, len(height) - 1
        while s < e:
            area = (e - s) * min(height[s], height[e])
            max_area = max(area, max_area)
            if height[s] < height[e]:
                s += 1
            else:
                e -= 1
        return max_area
public class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int s = 0, e = height.length - 1;
        while (s < e) {
            int area = (e - s) * Math.min(height[s], height[e]);
            maxArea = Math.max(area, maxArea);
            if (height[s] < height[e]) s++;
            else e--;
        }
        return maxArea;
    }
}
function maxArea(height: number[]): number {
  let maxArea = 0;
  let s = 0;
  let e = height.length - 1;
  while (s < e) {
    const area = (e - s) * Math.min(height[s], height[e]);
    maxArea = Math.max(area, maxArea);
    if (height[s] < height[e]) s++;
    else e--;
  }
  return maxArea;
}
func maxArea(height []int) int {
	maxArea := 0
	s, e := 0, len(height)-1
	for s < e {
		area := (e - s) * min(height[s], height[e])
		maxArea = max(area, maxArea)
		if height[s] < height[e] {
			s++
		} else {
			e--
		}
	}
	return maxArea
}
impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut max_area = 0;
        let (mut s, mut e) = (0, height.len() - 1);
        while s < e {
            let area = (e - s) as i32 * height[s].min(height[e]);
            max_area = area.max(max_area);
            if height[s] < height[e] {
                s += 1;
            } else {
                e -= 1;
            }
        }
        max_area
    }
}

이 풀이는 하나의 while 루프를 사용하여 너비를 계속 줄여나가기 때문에 소요되는 시간은 주어진 배열의 길이에 비례합니다. 따라서 시간 복잡도가 O(n)로 향상되어 LeetCode에서 잘 통과할 것입니다.