[4월 15일] container-with-most-water

📙 1. 문제

Link : https://leetcode.com/problems/container-with-most-water/description/

문제 설명

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

제한 사항

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

 

풀이 1 : 시간초과 풀이

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let answer = 0;
    for(let i=0;i<height.length;i++){
        for(let j=0;j<i;j++){
            answer = Math.max((i-j)*Math.min(height[i],height[j]),answer)
        }
    }
    return answer
};

• 혹시나 했지만, 역시나 시간 초과가 떴다.
• 시간 복잡도는 O(n**2)이고, n의 최대가 10^5이니, 최대 반복 수 10^10이니 그럴 만도..

풀이 2 : 투 포인터 사용

/**
 * @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;
};

• 투 포인터를 이용하면 간단하게 풀리는 문제였다.
• 너비가 크려면 x축과 y축 모두 커야 한다. x축을 벌리기 위해 start와 last변수를 양 쪽 끝에 두고 시작을 했다. y축은 각각의 height배열이 가지고 있기에 하나씩 순회하면서 비교할 것이다.
• height [start]와 height [last] 중 작은 값을 standard변수에 넣고, 두 사이의 거리(gap)를 구한다. 두 값 중 start가 작다면 start++, last가 작다면 last--하여 점점 좁혀준다.

---

🤔 2. 느낀 점

'어떤 알고리즘'을 사용해야 하는 지만 알면 쉽게 풀리는 문제였다. 그러기 위해서는 '어떤 알고리즘'이 있는지, 그리고 문제에서는 어떻게 적용이 되는지 꾸준히 문제를 풀어보며 숙달해야겠다고 생각했다.

 

🤩 3. 한 번 더 짚고 갈 점

부피가 커야 한다 => 양 두 지점이 멀리 떨어져 있어야 한다 => 투 포인터!