[LeetCode] Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=leetcode-75

 

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

 

n개의 숫자로 이루어진 height라는 배열이 있고, 각 i번째 요소에 대해서

(i,0)과 (i, height[i]) 가 이어진 선을 그래프로 그리고, 그 선들 중 두 개의 선으로 만들 수 있는 가장 넓은 면적을 구하는 문제다.

단, 두 선의 높이가 다를 경우 더 낮은 선을 기준으로 면적을 구해야 한다. (기울어진 선이 없음)

 

 

문제 풀이

function maxArea(height) {
  let result = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = height.length-1 ; j > i; j--) {
      let container = (j - i) * (height[i] > height[j] ? height[j] : height[i]);
      if (container > result) {
        result = container;
      }
    }
  }
  return result;
}

 

처음에는 단순하게 이중 for문을 돌렸는데, 정답은 잘 나왔지만..

배열이 어느 정도 길어지면 소요시간이 너무너무너무너무 길어지는 비효율적인 구조였다.

 

계속 고민을 하다가.. 겨우 다른 사람의 솔루션과 힌트를 참고해서 다시 작성한 코드는 아래와 같음.

 

function maxArea(heights) {
  let left = 0;
  let right = heights.length - 1;
  let container = 0;

  while (left < right) {
    container = Math.max(container, (right - left) * Math.min(heights[left], heights[right]));

    if (heights[left] < heights[right]) {
      left++;
    } else {
      right--;
    }
  }
  return container;
}

 

좌우 포인터의 현재 높이를 비교해서 더 낮은 쪽은 옮기는 방식이다.

이렇게 하면 내가 처음에 생각한 것처럼 불필요하게 for문을 n*n-1만큼 돌릴 거 없이,

그냥 중간엔서 자연스럽게 만나게 되는 구조가 된다.

 

다른 사람의 솔루션을 참고해서 겨우 통과했다는 게 좀 분하지만...

그래도 여태까지는 pointer를 for문을 이용해 규칙적으로 증감시키는 방식으로만 사용해 왔는데,

이 문제를 통해 선택적으로 pointer를 옮기는 방식도 있다는 걸 깨달았다는 점에서는 의미가 있었다.