[java] Container With Most Water

[참고문제] : https://leetcode.com/problems/container-with-most-water/

Container With Most Water - LeetCode

문제 풀이

간단히 2중 포문으로 풀 수 있겠지만, Time 제한에 걸릴게 뻔해보였다.

 

생각의 흐름 - 일단 2중 포문으로는 잘 구현되는지 보자.

이중포문을 구현했지만 역시나 시간 이슈가 생겼다.

 

생각의 흐름 - 양쪽에서 줄여나가자.

늘 그렇듯, 이런 문제는 양쪽에서 줄여나갈 필요가 있다.

left, right 인덱스를 설정하고 총량을 계산해, MAX를 비교하고자 했다.

 

생각의 흐름 - 언제 left와 right를 늘리거나 줄여주는가?

while문은 left와 right가 같지 않을때로 설정하면 될 것으로 보였다.

그러나, 언제 left를 늘리고, 언제 right를 줄이는지 제한이 있어야 했다.

예시 문제를 통해 볼 때, 중간에 매우 긴 벽이 있을수도 있었다.

left와 right를 비교해야만 할 것으로 보였고, width를 같이 고민했다.

width가 줄어드는 것보다 더 이득일 경우에만 늘려야 한다고 판단했으나, 그러면 이중 포문과 다를 것이 없었다.

그럼 약간 Greedy하게 보기로 했다. 당장 left와 right중 작은게 결국 문제가 될 것이고, 작은걸 변화시키자고 생각했다.

left와 right를 비교했을 때 더 작은 것을 변화시켰다.

 

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxMount = 0;

    while(left != right) {
        int width = right - left;
        maxMount = Math.max(width*(Math.min(height[left], height[right])), maxMount);
        if(height[left] > height[right]) {
            right --;
        } else {
            left ++;
        }
    }
    return maxMount;
}