[ leetcode 문제풀이 ] Container With Most Water

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

Container With Most Water - LeetCode

(Container With Most Water 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Container With Most Water 문제 설명 >

 

Container With Most Water 문제는 다음과 같다.

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.

 

길이 n의 정수배열 height 가 주어진다. height는 height[i]의 양 끝이 (i,0), (i, height[i])인 n개의 수직선으로 이루어져 있다. x축과 함께 height의 2개의 선이 구성하는 컨테이너가 물을 가장 많이 담도록 하는 경우를 찾아 가장 많이 담을 수 있는 물의 양을 리턴하여라. 컨테이너를 기울일 수 없다.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 n == height.length, 2 ≤ n ≤ 10^5, 0 ≤ height[i] ≤ 10^4 이다.

 

 

 

---

< Container With Most Water 문제 설명 >

 

그냥 height의 가능한 모든 쌍을 훑어보는 것은 아닌거 같고, 어떻게 접근해야 할지 느낌이 안 와서 힌트를 봤다.

The aim is to maximize the area formed between the vertical lines. The area of any container is calculated using the shorter line as length and the distance between the lines as the width of the rectangle.
Area = length of shorter vertical line * distance between lines

We can definitely get the maximum width container as the outermost lines have the maximum distance between them. However, this container might not be the maximum in size  as one of the vertical lines of this container could be really short.

힌트에서의 핵심은 distance between line 이 area에 영향을 미치는 요인임을 고려하라는 것이다. 가장 바깥의 두 선을 골라 정해지는 maximum width container 가 비록 maximum size를 만들지 않는다 할 지라도 중요한 것은 이보다 높이가 낮은 container은 고려할 필요가 없다는 것이다.

 

즉, maximum width container에서 현재 상태보다 높이가 높은 line을 찾아 container의 너비를 좁혀가며 container의 size를 체크한다. 이때, container의 높이를 결정짓는 것은 좌,우 line의 높이 중 작은 값이므로 작은 높이의 line을 변경하는 방식으로 탐색한다. 이를 코드로 나타내면 다음과 같다. (Cpp 사용)

 

    int maxArea(vector<int>& height) {
        int left = 0, right = height.size()-1;
        int max_water = 0;
        
        do{
            bool MaxValue = true;
            if(height[left] < height[right]){
                max_water = max(max_water, height[left]*(right-left));
                for(int i=1;i<right-left;i++)
                    if(height[left] < height[left + i]){
                        left += i;
                        MaxValue = false;
                        break;
                    }
            }
            else{
                max_water = max(max_water, height[right]*(right-left));
                for(int i=1;i<right-left;i++)
                    if(height[right] < height[right-i]){
                        right -= i;
                        MaxValue = false;
                        break;
                    }
            }
            if(MaxValue) break;
        }while(left < right);
        return max_water;
    }

 

위 코드에서 do while loop를 탈출하는 방법은 2가지이다. 

1) left == right가 된 경우: 이는 너비가 1인 경우까지 탐색을 완료한 경우에 해당한다.

2) MaxValue가 true인 경우: 현재 선택한 두 line 사이에 컨테이너의 높이보다 더 높은 line이 존재하지 않는 경우에 해당한다. 이 경우는 내부 컨테이너가 현재보다 반드시 작은 size를 가지므로 탐색해줄 필요가 없다.

 

 

높이가 같은 두 line으로 컨테이너가 구성되었을 때, 이보다 더 높은 line을 찾아 업데이트 하는 것을 오른쪽 line으로만 단정해도 되는 것인가? 하는 의문이 들었다. (height[left] == height[right]일 때 right만 옮기는 것이 합당한가?)

 

이에 대한 결론은 right를 업데이트 하던지, left를 업데이트 하던지 그 결과는 같다는 것이다.

 

container의 size를 계산하는 것에서 중요한 점은 두 line의 높이 중 최솟값이 container의 높이가 된다는 것이다. 예를 들어 left를 k (left < k < right, height[left] < height[k])로 업데이트 했다고 하면 새로 만들어지는 컨테이너의 높이는 height[right]로 결정된다. 이후 진행되는 높이의 업데이트는 반드시 height[right]에 대해 진행되는 것이다. 즉, 높이가 같은 line left, right의 업데이트는 그저 순서의 차이일 뿐 같은 탐색 결과를 낳는다.

 

두 line을 선택할 수 있는 모든 경우를 탐색하지는 않았지만, 고려할 필요가 없는 case를 제거해 탐색의 범위를 상당히 줄일 수 있었다.