11. Container With Most Water

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

Container With Most Water - LeetCode

 

 

 

1. 문제와 예제, 그리고 제약사항

 

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

 

2. 문제 풀이

 

문제를 해석하면 다음과 같다. 배열이 주어지고 각각 배열의 값은 y축인 높이 값이 담겨있다. x축(즉, 배열의 index값), y축(배열의 높이 값)을 하나의 컨테이너라고 보고 이 컨테이너에 가장 많은 물을 담을 수 있는 값을 반환하면 된다.

 

예제1과 같이 index = 1의 높이는 8이고 index = 8의 높이는 7이 된다. index 1, 8을 선택하여 컨테이너를 구성하면  (8-1) * 7 = 49가 되면서 가장 많은  물을 담을 수 있게 된다.

 

이 문제는 보통 이중 for 문을 풀면 쉽게 풀이가 가능하다. 그러나 이중 for문을 사용시에 Time Limit Exceeded가 발생하게 된다. 한개의 반복문만을 사용하여 풀기 위해 슬라이딩 윈도우 알고리즘을 적용하면 풀이가 가능하다.

 

1. 먼저 컨테이너 양쪽 끝을 시작으로 넓이 값을 구한다.

2. 이때 높이는 최대 값이 아닌 양쪽 끝점의 최소값을 이용해야 한다.

3. 왼쪽 끝점과 오른쪽 끝점을 이동하여 다른 양 끝점일 때의 넓이 값을 구해본다.

- 왼쪽 끝점의 높이 값이 오른쪽 끝점의 높이 값보다 큰 경우에는 오른쪽 끝점을 왼쪽으로 이동한다.

- 반대로 왼쪽 끝점의 높이 값이  오른쪽 끝점의 높이 값보다 작은 경우에는 왼쪽 끝점을 오른쪽으로 이동한다.

-> 컨테이너의 높이 값은 더 작은 쪽의 높이 값이 된다. 그렇기 때문에 왼쪽과 오른쪽 각각의 끝점의 높이 값 중  더 작은 쪽을 이동 시켜야 한다. 만약 더 큰쪽의 값을 변경시켜버리면 여전히 높이는 기존의 더 작은 높이 값을 유지하기 때문이다.

4. 새롭게 구한 넓이 값과 기존에 계산한 넓이 값을 비교하여 더 큰 값을  저장한다.

 

 

이를 구현한 소스 코드는 아래와 같다.

class Solution {
    public int maxArea(int[] fdheight) {        
        int l=0;
        int r = fdheight.length -1;        
        int sum = 0;
        int answer = 0;
        
        while( l<r ){         
            sum = (r-l) * Math.min(fdheight[l], fdheight[r] );
            answer = Math.max(sum, answer);
             
            if( fdheight[l] > fdheight[r]){
                r--;
            }else{
                l++;
            }
        }
        return answer;
    }
}