[CT-L] 11. Container With Most Water

문제 설명

Medium

• 길이가 n인 정수 배열 높이가 제공되며, i번째 선의 두 끝점이 (i, 0) 및 (i, height[i])가 되도록 n개의 수직선이 그려집니다.
• 컨테이너에 가장 많은 물이 포함되도록 x축과 함께 컨테이너를 형성하는 두 개의 선을 찾으십시오.
• 컨테이너가 저장할 수 있는 최대 물의 양을 반환합니다.

 

접근

첫번째.

var maxArea = function(height) {
    let result = [];
    
    for (let i=0; i<height.length-1; i++) {
        for (let j=i; j<height.length-1; j++) {
            if (height[i] < height[j+1]) {
                result.push(height[i] * (j-i+1));
            } else {
                result.push(height[j+1] * (j-i+1));
            }
        }
    }
    
    return Math.max.apply(null, result);
};

• for 문을 2번 돌아 모든 넓이 값을 result 배열안에 push 한 후, Max 함수를 이용하여 가장 큰 넓이를 반환했다.
• 하지만 런타임 에러 발생... 좀 더 효율적인 로직을 구성해야만 했다.

 

두번째.

var maxArea = function(height) {
    let result = 0;
    
    for (let i=0; i<height.length; i++) {
        for (let j=i+1; j<height.length; j++) {
            result = Math.max(result, Math.min(height[j], height[i]) * (j - i));
            // console.log(result);
        }
    }
    
    return result;
};

• result 초기 값 0으로 설정 후, for 문을 2번 돌아 모든 넓이 값을 구하면서, result 값을 Max 함수로 비교해가면 넓이 값을 교체하였다.
• 하지만 런타임에러... 다시 좀 더 효율적인 코드가 필요하다.

 

세번째.

var maxArea = function(height) {
    const n = height.length;
    
    let max = 0;
    let left = 0;
    let right = n - 1;
    
    while (left < right) {
        const area = (right - left) * Math.min(height[left], height[right]);
        
        max = Math.max(max, area);
        
        if (height[left] < height[right]) left++;
        else right--;
    }
    
    return max;
};

• 좌, 우 끝에서부터 접근하여, 2번의 for 문을 사용하지 않고 Max 함수를 사용하여 큰 넓이 값으로 교체하며 접근한다.
• 좌측 높이가 우측 높이보다 작을 경우 left 증가, 우측이 높을 경우 right 감소를 하여 최단 접근을 할 수 있게된다.

 

후기.

문제에서 주어진 값들을 순차적으로만 찾으려 하지않고, 최단 접근을 할 수 있도록 연습해야겠다.

 

 

Container With Most Water - LeetCode