[LeetCode, 리트코드] Container With Most Water

1. Problem

 

주어진 (i, ai) 좌표를 나타내는 a1, a2, ..., an 정수들이 있다. n 개의 수직선들은 (i, 0), (i, ai)을 두 끝점으로 그려진다. 두 개의 수직선으로 아래와 같이 가장 많은 물을 담을 수 있는 용기를 만들고 그 최대 용량을 구하라. ( n은 최소 2 이상 )

 

 

위의 그림의 수직선들은 [1,8,6,2,5,4,8,3,7]로 나타내어진다. 이 경우 가장 큰 용량은 49이다. (파란색으로 칠한 부분)

 

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

 

2. Solution

 

여기서 중요한 포인트는 물의 넓이가 더 작은 막대기에 의해서 좌우된다는 것이다. 처음에 양 끝단점을 가르키는 두 개의 포인터 i, j를 놓은 다음 이보다 더 큰 넓이를 찾아가는 식으로 알고리즘이 진행된다.

 

가장 큰 수평 길이일 때의 초기 넓이를 생각해보자(0, length - 1). 이보다 더 큰 경우가 나올 경우는 현재의 작은 막대기의 크기가 이보다 더 큰 작은 막대기로 이루어진 용기가 만들어질 경우다. 이 때 (작은막대기 * 두 막대기 사이의 거리)를 구할 때 이보다 더 큰 물의 넓이가 나오면 이것을 업데이트하는 방식으로 진행하면 문제를 풀 수 있다.

 

 

3. What I solved

class Solution {
public:
    int maxArea(vector& height) {
        int left = 0;
        int right = height.size() - 1;
        int max_area = (right - left)*min(height[left], height[right]);
        while(left < right){
            if(height[left] <= height[right]){
                left++;
            }
            else {
                right--;
            }
            
            max_area = max(max_area, (right - left)*min(height[left], height[right]) );
        }
        
        return max_area;
    }
};