[LEETCODE - 15] Container With Most Water 풀이

문제파악

 

문제는 그래프 내에서 높이(height) 를 알수 있는 배열 `heights` 가 주어졌을때, 위 그림과 같이 주어진 그래프에서 가장 많은 물을 차지할수 있는 컨테이너를 찾는 것 이다. 일단 가장 간단하게 생각해보았을때, 물의 면적을 구하는 공식은 아래와 같이 구할수 있을 것 이다.

 

컨테이너의 용량구하기

공식: \( \text{Volume} = \text{Width} \times \text{Height} \)

생각해보면 우리는 이미 받은 height 배열을 통해 그래프내 막대들의 높이는 이미 알고 있는 상태이다.

heights = [1,8,6,2,5,4,8,3,7]

 

하지만 widths 는 알지 못한다. 따라서 우리가 구해야 하는 것은 이 widths 를 어떻게 구할 것인지를 생각해야 하는 것이 이 문제의 가장 큰 핵심이라고 볼 수 있다. 문제를 풀때 항상 가장 간단한 방법을 찾고, 이제 다른 방법으로 풀수 있는지 혹은 최적화(Optimization) 이 가능한지를 찾아본다.

간단한 방법

일단 이 문제를 생각해봤을때 가장 간단한 방법은 알아낼 수 있는 모든 컨테이너의 크기를 알아내게 된후 그 중 가장 큰 컨테이너를 고르면 정답으로 유추할 수 있다. 가장 쉬운 방법으로는 아래와 같은 수도 코드로 기술해볼 수 있겠다.

val maxSizeOfContainer = 0
val n = size(heights)
for i to (n - 1):
	w1, h1 = i, heights[i]
    for (i + 1) as j to n:
    	w2, h2 = j, heights[j]
        result = (w2 - w1) * min(h1, h2)
        maxSizeOfContainer = max(maxSizeOfContainer, result)

return maxSizeOfContainer

 

매우 직관적인 코드이며 O(N^2) 의 시간 복잡도를 가지는 코드로 시간이 오래걸리겠지만 문제풀이는 가능한 형태이다.

 

코드를 가볍게 설명하자면 result(sizeOfContainer) 를 구할때 작은 높이를 취하는 이유는 높은 높이를 취한뒤 계산하게 되면 작은 높이의 구간에서 흘러넘치(overflow)는 현상이 발생할 수 있기 때문이다. 따라서 둘중 작은 높이를 취해야 한다. 이렇게 하게 되면 leetcode 의 대부분의 testcase 는 통과하나 heights 의 사이즈가 큰 문제들이 통과하지를 못한다. 따라서 어떻게 최적화를 해야할지 고민해야 하는 단계이다.

 

가장 쉬운 최적화로는 아래와 같이 이미 계산된 결과는 계산하지 않는 결과를 해볼수도 있다.

val maxSizeOfContainer = 0
val cache = {}
val n = size(heights)
for i to (n - 1):
	w1, h1 = i, heights[i]
    for (i + 1) as j to n:
    	w2, h2 = j, heights[j]
        width = w2 - w1
        height = min(h1, h2)
        if cache[width] == height:
        	# don't calculate anymore
        	continue
        result = width * height
        maxSizeOfContainer = max(maxSizeOfContainer, result)

return maxSizeOfContainer

 

하지만 위의 방식은 만약 동일한 width, height 의 계산량이 많다면 시도해 볼만 하지만 곱연산 자체의 부하도 크지 않을 뿐더러 시간 복잡도 자체의 영향을 주지 못하고 메모리 사용량 또한 증가하므로 별로 좋은 최적화는 아니다.

시간 복잡도를 줄이자

시간 복잡도를 줄이기 위해서는 이 문제를 풀기 위해 설계된 알고리듬의 순차도가 변경되어야 한다. 이 경우 두개의 그래프(포인터)를 찾고, 범위를 좁혀나가면서 값을 구하는 문제로 보이므로 투 포인터 알고리즘(Two pointer algorithm) 을 통해 해결방안을 모색해 볼 수 있다.

 

예를 들면 우리가 가지고 있는 height 은 아래와 같다.

[1,8,6,2,5,4,8,3,7]

 

여기서 witdh 를 구하는 방법은 각 구간의 index 를 사용하면 된다.

[0,1,2,3,4,5,6,7,8]

---

[0,1,2,3,4,5,6,7,8]
 L               R

 

위와 같이 양 극단에 L 과 R 포인터를 두게 되었을때 각 width 와 height 은 (8 - 0), min(1, 8) 의 값을 가진다. 그래서 L 이 (0) R 이 (7) 에 있었을때의 컨테이너의 사이즈는 8 * 1 인 = 8 을 가지게 된다. 이렇게 되었을때 width 는 L 또는 R 포인트를 서로에 가깝게 좁히면 좁힐수록 좁아질수 밖에 없으므로 따라서 우리가 움직이지 않고 고정시켜야 하는 포인터는 둘중 높이가 높은 R 포인트이게 된다.

[0,1,2,3,4,5,6,7,8]
   L             R

 

위와 같은 프로세스를 계속 반복하다보면 어느순간 L 과 R 이 만나는 순간이 오는데 그 순간 알고리듬을 종료시키면 된다. 위 프로세스를 수도 코드로 적어보면 아래와 같을 것이다.

    def maxArea(self, height):
        L, R = 0, len(height) - 1
        answer = 0
        while L < R:
            width = R - L
            h = min(height[L], height[R])
            result = width * h
            answer = max(answer, result)
            if height[R] > height[L]:
                L += 1
            else:
                R -= 1
        return answer

 

위와 같이 입력하게 되면 시간복잡도 O(N) 안에 문제 풀이가 끝나게 된다.