[Leet Code Top 100] #11. Container With Most Water

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

최악의 경우 막대 중 2개를 선택해서 최대 Area 를 비교할 수 있기 때문에 시간은 O(N^2) 보다 효율적으로 풀어야 합니다. 우선 O(N log N) 을 먼저 고려했을 때 대표적으로 Binary Search 같은 알고리즘을 생각할 수 있는데 정렬이 되지 않아 컨셉에 맞지 않았습니다.

풀이에 중점을 둬야할 부분이 넓고 낮은 Area 와 좁고 높은 Area 를 비교하는 것 입니다. 최대 높이를 기준으로 for loop 를 돌면서 계산할 경우 height 가 10의 4승까지 가능했기 때문에 최대 너비를 기준으로 left 와 right 를 비교하는 two-pointers 알고리즘으로 풀이 방향을 정했습니다.

핵심적인 부분은 left 와 right 를 줄여나가는 부분인데 순차적으로 Area 를 계산하기 위해서는 left 와 right 가 같이 변경되서는 안됩니다. 둘 중 낮은 height 를 계속 바꿔야 Area 가 더 넓어질 수 있으므로 height[left] 와 height[right] 를 비교하는 조건을 추가했습니다. 시간 복잡도는 O(N) 입니다.

 

소스 코드

// Leet Code
// #11. Container With Most Water
// Success
// Runtime: 149 ms, faster than 15.64% of JavaScript online submissions for Container With Most Water.
// Memory Usage: 47.9 MB, less than 73.84% of JavaScript online submissions for Container With Most Water.

function main(){
    // Input // Output
    //height = [1,8,6,2,5,4,8,3,7]; // 49
    //height = [2,3,4,5,18,17,6];
    height = [2,3,4,5,18,17,6];
    
    console.log(maxArea(height));
}

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;

    while(left < right){
        const curArea = Math.min(height[left], height[right]) * (right - left);
        if(maxArea < curArea){
            maxArea = curArea;
        }
        
        //console.log(`height[${left}]:${height[left]} / height[${right}]:${height[right]}`);

        if (height[left] < height[right]){
            left++;
        } else {
            right--;
        }

    }
    
    return maxArea;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - [JavaScript] O(n) time solution that's easy to understand
• [알고리즘] 투 포인터 (Two pointers) 알고리즘