[알고리즘 - LeetCode] Container With Most Water

김혜진·2019년 12월 5일

algorithms

목록 보기

7/8

문제

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

양의 정수로 이루어진 배열에서 인덱스는 x축, 숫자는 y축의 점을 나타낸다.
가로로 선을 그었을 때 가장 많은 양의 물을 담을 수 있는 컨테이너의 면적을 구하라.
참고: 컨테이너는 기울임 없이 직사각형으로 이루어지며 최소 값은 2이다.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
In this case, the max area of water (blue section) the container can contain is 49.

주어진 배열 [1,8,6,2,5,4,8,3,7] 은 위의 세로 선을 표시합니다.
이 경우 물이 담길 수 있는 컨테이너(파란색 부분)의 최대 면적은 49입니다.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

풀이

어째든 배열로 주어지는 모든 값을 한번 씩 순회하는 것이라 어려운 문제는 아니었으나 medium 레벨인 이유는 어떤 방식이 가장 효율적인가? 를 고민해야하는 문제이기 때문인 것 같다.
한 방향으로만 순회하게 되면 모든 값을 비교하기 위해서 시간 복잡도가 n2이 되어버려서 while문으로 양 끝에서 동시 비교하는 것으로 해결했다.

제출 코드

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let max = 0;
    let start = 0;
    let last = height.length - 1;
    
    while (last - start > 0) {
        const standard = height[last] > height[start] ? height[start] : height[last];
        const gap = (last - start) * standard;
              
        height[last] > height[start] ? start++ : last--;
        max = max < gap ? gap : max;
    }
    return max;
};

배열의 양 끝의 값을 start, last 변수에 담아서 각각의 값이 양 끝에서 whlie 문으로 순회를 시작한다.
이때 start와 last더 작은 값을 standard변수에 담아 y축을 정한다.
더 작은 값을 담는 이유는 컨테이너를 만드는 y축의 양 끝이 모두 막혀있어야 문제에서 말하는 '물을 담는' 컨테이너를 만들 수 있기 때문이다. 만약 더 큰 값을 담는다면 아래의 자료처럼 물이 넘치게 된다.

정해진 y축의 양 끝의 거리를 last - start값으로 계산해 x축을 정한다.
이때 standard로 정해졌던 값은 다음 순회에서 제외되게 된다. 다시 말해 start였다면 start를 하나 더해서 변경해주고, last였다면 last를 하나 빼서 변경해준다.
그래야 모든 값을 한번 씩 순회하는 것이 된다.
순회하며 x * y의 면적을 gap 변수에 담고 max 변수 값과 비교하여 더 큰 값을 max값으로 할당하고 순회를 마친 후 반환한다.