[Two Pointers][Medium] 11. Container With Most Water

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

Container With Most Water - LeetCode

 

Q. height 배열이 각 벽의 높이를 의미할 때, 물을 채운다고 하면 최대 면적을 구하라.

 

Solution. 

 area 는 width * height 이다. 이때 물을 채우는 경우를 가정하며, 계산하므로, height는 양쪽 벽중 낮은 쪽의 높이가 될 것이다. 또한 width 는 양벽까지의 거리가 될 것이다. 

이제 문제는 양벽을 어떤 식으로 이동시키며 이 면적이 최대인 경우를 찾는지가 될 것인데, 문제 조건은 최대의 면적을 구하는 것이다. 즉, 더 큰 결과를 갖는 것을 지향하면서 이동시키면 된다는 것이다. 

다시말해 두 벽에서 한쪽벽이 다른 벽보다 낮으면, 낮은 쪽 벽을 이동시키면 되는 것이다. (그래야 더 큰 값을 얻을 확률이 생기므로.)

두 벽의 높이가 같다면? 이 경우는 이제 check가 되었으므로, 모두 다음 벽으로 넘어가면 된다. 이것이 가능한 이유는 오직 낮은 쪽의 높이만이 유효한 과정값으로 사용되기 때문이다. 

 

int maxArea(vector<int>& height)
{
    // 각 height에 해당하는 높이에 물을 채운다고 할때, 
    // 최대 면적을 구하라.
    //
    int left = 0;
    int right = height.size() - 1;
    int maxArea = 0;
    while (left < right)
    {
        int h = min(height[left], height[right]);
        maxArea = max(maxArea, h * (right - left));
        if (height[left] > height[right])
            --right;
        else if (height[left] < height[right])
            ++left;
        else
        {
            ++left; --right;
        }
    }
    return maxArea;
}