LeetCode - Container With Most Water (Javascript)

문제 설명

막대기 사이의 거리 * 높이를 통해 물을 가장 많이 담을 수 있는 경우의 수를 구하는 문제였다.

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.

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

Constraints:

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

---

소스 코드 (1차 시도)

시간 초과가 나버렸다…
완전탐색 방식으로 작성해서 그런 것 같은데, 아무래도 그리디 방식으로 풀이를 해야되는 것 같다.

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

---

소스 코드 (2차 시도)

통과가 되긴 했지만, 역대급으로 처참한 시간복잡도가 나와버렸다..
통과 됐다고 해야하나 싶을 정도다ㅜ

function maxArea(height) {
  let answer = 0;
  let size = 0;
  let maxHeight = 0;
  let maxEndHeight = 0;
  for (let i = 0; i < height.length; i++) {
    if (maxHeight >= height[i]) continue;
    maxHeight = height[i];
    maxEndHeight = 0;
    for (let j = height.length - 1; j > i; j--) {
      if (maxEndHeight >= height[j]) continue;
      maxEndHeight = height[j];
      size = (j - i) * Math.min(height[i], height[j]);
      answer = Math.max(answer, size);
    }
  }
  return answer;
}

---

소스 코드 (최종)

while문을 활용했고, 포인터 이동 로직을 조금 더 간결하게 변경하여 시간복잡도를 개선할 수 있었다.

function maxArea(height) {
  let result = 0;
  let left = 0;
  let right = height.length - 1;
  let size;
  while (left < right) {
    size = (right - left) * Math.min(height[left], height[right]);
    if (size > result) result = size;
    if (height[left] < height[right]) left++;
    else right--;
  }
  return result;
}

---

풀이 과정

그리디 알고리즘의 핵심은, 모든 경우의 수를 탐색하는 것이 아니라, 가능성 없는 경우의 수는 버리고 탐색할 가치가 있는 경우에만 탐색을 실행하는 것이라고 생각한다.

이에 따라 높이가 높은 막대기를 하나 잡아두고, 높이가 더 낮은 막대기의 포인터를 움직이는 방식으로 로직을 짰다. 아래와 같이 left는 시작점 0에서, right는 끝(height.length-1)에서 시작한다.

그리고 left와 right의 비교를 통해 더 작은쪽이 움직이도록 한다.

이런식으로 left와 right 포인터를 움직이며 탐색을 하면, 모든 경우의 수를 탐색하는 것이 아니라 거리별(right-left) 최대값을 구하는 방식의 그리디 알고리즘 로직을 따르게 된다.

그리고 이는 매 반복마다 포인터가 반드시 한 번씩은 움직이기 때문에 시간복잡도 또한 O(N)으로 굉장히 효율적이라고 볼 수 있다.

---