[리트코드] 11. Container With Most Water / Javascript

문제주소 :https://leetcode.com/problems/container-with-most-water/

Container With Most Water - LeetCode

---

<문제 설명>

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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: 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.

Example 2:

Input: height = [1,1] Output: 1

Example 3:

Input: height = [4,3,2,1,4] Output: 16

Example 4:

Input: height = [1,2,1] Output: 2

 

Constraints:

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

 

<풀이법>

▒ 한줄 개념: 좌우 포인터 ▒ 

좌우 포인터라 함은, 왼쪽에서 출발해서 오른쪽으로 가는 toRight 포인터와, 오른쪽에서 출발해서 왼쪽으로 가는 toLeft 포인터를 사용하여 알고리즘을 구현하는 것을 의미하고자 했습니다.(기존에 존재하는 알고리즘인지는 모르겠습니다.)

 

간단하게 풀이과정을 요약하면, 다음과 같습니다.

1. 변수 초기화(toRight = 0, toLeft = n-1)
2. while(toRight < toLeft)
  2-1. toRight, toLeft 기반 넓이값 계산하여 answer값 비교 및 갱신
  2-2. toRight, toLeft 의 높이를 비교하여, 더 낮은 값의 포인터 이동
  2-3. 포인터 이동시, 기존보다 높은 높이가 나올 때까지 이동

 

우선 물이 들어갈 수 있는 넓이를 구하는 방식은 두 막대기의 너비 * 더 짧은 막대기의 높이가 됩니다.

그럼 여기서 가장 쉽게 이 문제를 풀 수 있는 방법은, 완전탐색일겁니다. 왼쪽부터 시작해서 막대기를 하나씩 고르고, 해당 막대기의 오른쪽에 있는 모든 막대기들과의 넓이를 구한 뒤 그 중 최댓값을 구하면 될 것 같습니다. 

하지만 막대기의 갯수가 최대 10^5 개이기 때문에, 해당 방식으로 하면 O(nlogn)이 나와서 시간복잡도가 될지 잘 모르겠네요. 될 것 같기는 하지만, 시간이 좀 더 걸릴 것 같네요.

 

따라서 제가 선택한 방식은 위에서 말한대로 좌우 포인터 방식입니다. 0부터 시작해서 n-1까지 가는 toRight, n-1부터 시작해서 0까지 가는 toLeft를 선언한 뒤, 둘을 움직이면서 둘 사이의 넓이 값을 계산합니다. 

 

이 경우 두 포인터를 어떻게 움직이는지가 중요한데, 기본적으로 toLeft, toRight 모두 한번 움직이기 시작하면 현재 자신보다 큰 높이를 만나서야 멈추도록 하였습니다.

위의 toLeft 포인터를 예로 들면, toLeft는 8번 idx 에서 시작한 상태로, 높이는 7을 가리키고 있습니다. toLeft가 움직인다고 가정했을 때, 바로 왼쪽인 7번 idx에서 멈췄다고 가정하면, 높이로 3을 가지게 되므로, 8번 idx를 가리키던 시작상태에서 보다 작은 넓이를 무조건 가질 수 밖에 없습니다. 왼쪽으로 이동하면서 너비가 감소하는데, 더 작은 값을 만나 높이까지 감소한 상태이기 때문입니다. 결과적으로, 좌우 포인터는 모두 기존보다 큰 높이의 막대에서 멈춘 뒤에 계산해야, 기존보다 큰 넓이값을 가질 수 있습니다.

 

그럼 마지막으로, 현재 넓이 값을 계산한 후, 좌우 포인터 중 어떤 포인터를 먼저 움직여야할지의 문제가 남았습니다.

이 문제는 그리디하게 toRight과 toLeft 중 낮은 높이의 포인터를 움직여주는 방식으로 구현해주었습니다. 이 이유는, 어차피 최대 넓이를 구해야하는 문제이므로, 높이가 작은 쪽을 더 크게 바꿔주어야 넓이가 커질 가능성이 있기 때문입니다. 

 

<코드(Javascript)>

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    const n = height.length;
    let toRight = 0;
    let toLeft = n-1;
    let answer = 0;
    
    while(toRight < toLeft){
        const val = (toLeft - toRight) * min(height[toRight], height[toLeft]);
        answer = val > answer ? val : answer;
        
        if(height[toLeft] < height[toRight]){
            const curLeft = height[toLeft];
            while(toLeft >= 0 && height[toLeft] <= curLeft){
                toLeft--;
            }
        }else{
            const curRight = height[toRight];
            while(toRight < n && height[toRight] <= curRight){
                toRight++;
            }
        }               
    }
    
    return answer;
};

const min = (a, b) => a < b ? a : b;

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest