[leetcode] 11. Container With Most Water

11. Container With Most Water

 

Greedy 카테고리에서 첫 문제였는데, 백준에서 푼 기억이 있다. (아닌가..?)

 

풀이 코드는 총 두 개인데 하나는 5ms, 다른 하나는 4ms이다.

 

1. 첫 풀이

 

이중 for문을 돌려서 앞에서부터 마지막 기둥 간의 면적을 모두 체크해야한다고 생각했다.

단순히 길고 높은 기둥이 시작 혹은 마지막에 있다고 해도 적당히 짧고 긴 기둥들과 기둥 간의 거리가 생각보다 멀면 면적이 훨씬 넓게 나올 수 있기 때문이다.

 

다만 시작에 위치하게 될 기둥의 길이가 앞서 체크했던 기둥보다 짧을 경우엔 체크하지 않도록 했다.

배열의 길이가 최대 10^5이기 때문에 스킵할 조건을 체크해주는 게 중요하다고 생각했다.

 

이러한 로직으로 풀이하게 될 경우 통과할 수는 있지만 최악의 케이스인 배열이 오름차순일 경우 시간 초과가 될 수도 있겠다는 생각이 들어서 새로운 풀이를 고민하였다.

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int maxAmount = 0;
        for(int i = 0; i < height.length; i++) {
            if (max >= height[i]) { // 이전에 나온 시작 기둥 길이보다 짧을 경우 스킵
                continue;
            }
            if (max < height[i]) {
                max = height[i];
            }
            
            for(int j = i + 1; j < height.length; j++) {
                int amount = Math.min(height[i], height[j]) * (j - i);
                if (maxAmount < amount) {
                    maxAmount = amount;
                }
            }
        }
        return maxAmount;
    }
}

 

2. 두번째 풀이

 

결국 시작과 끝만 고려하면 된다는 생각이 들어서 two pointer를 사용해서 문제를 풀었다.

left와 right에 각각 0과 배열의 끝 인덱스를 넣고 최대 면적을 계산하였다.

height[left]가 height[right]보다 클 경우 right를 왼쪽으로 이동시키고, 반대의 경우에는 left를 오른쪽으로 이동시켰다.

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

        while(left < right) {
            int amount = Math.min(height[left], height[right]) * (right - left);
            if (amount > maxAmount) {
                maxAmount = amount;
            }
            if (height[left] > height[right]) {
                right -= 1;
            } else {
                left += 1;
            }
        }
        return maxAmount;
    }
}