[leetcode] 11. Container With Most Water

 

 

이문제를 처음 접했을때는 가로는 가장 넓은 거를 기준으로 잡고

높이는 가장 높은거로 하면되겠다 이렇게 막연한 생각만 들었었다.

 

벽으로 문제를 푼다고 상상해보자

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

벽이 여러개 세워져 있는 모양으로 각 숫자는 벽의 높이고, 벽 사이에 물을 채울 수 있다.

 

첫번째 개념 : 어떤 두변 사이에 물을 담을 수 있다.

예를 들어 왼쪽 벽 높이가 8, 오른쪽 벽이 6이면 아무리 왼쪽이 높아도 낮은 벽 높이만큼 물을 담을수있다.

즉, 물의 높이는 두벽중 작은 높이

 

두번째 개념 : 너비도 중요하다

벽 사이의 거리가 멀수록, 물을 더 많이 담을 수 있다.

즉, 물의 양은 (작은 높이) x (두 벽 사이의 거리)

 

전략: 최대 물을 담기위해 두 끝에서 시작한다

1. 처음앤 맨 왼쪽과 맨 오른쪽에서 시작한다 → 이렇게하면 일단 너비는 최대
2. 두벽 사이의 물의 양을 계산 → 작은쪽 높이를 기준으로 x 거리
3. 그다음 더 낮은 쪽의 벽을 한칸 안으로 이동한다
4. 이걸 계속 반복하면서 최대값을 업데이트한다

 

첫번째 결과물

var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let maxNum = 0;
  let tempWidth = 0;

  while (left < right) {
    const width = right - left; // 거리
    if (height[left] > height[right]) {
      tempWidth = width * height[right];
    } else {
      tempWidth = width * height[left];
    }

    if (maxNum < tempWidth) {
      maxNum = tempWidth;
    }

    left++;
  }
  return maxNum;
};

Math.min 으로 비교값 간단화하기

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height: Array<number>) {
  let left = 0;
  let right = height.length - 1;
  let maxNum = 0;
  let tempWidth = 0;

  while (left < right) {
    const width = right - left; // 거리

    tempWidth = width * Math.min(height[left], height[right]); // -------------------> 변경
    if (maxNum < tempWidth) {
      maxNum = tempWidth;
    }

    left++;
  }
  return maxNum;
};

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));

변수명 바꾸기

최대면적 , 최소면적으로 보기쉽게 mexNum, tempWidth에서 area, maxArea로 바꿨다

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height: Array<number>) {
  let left = 0;
  let right = height.length - 1;
  let maxArea = 0; // -------------------> 변경
  let area = 0; // -------------------> 변경

  while (left < right) {
    const width = right - left; // 거리

    area = width * Math.min(height[left], height[right]);
    maxArea = Math.max(area, maxArea);

    left++;
  }
  return maxArea;
};

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));

(추가)두개 포인터 값비교후 작은값이 이동

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height: Array<number>) {
  let left = 0;
  let right = height.length - 1;
  let maxArea = 0;
  let area = 0;

  while (left < right) {
    const width = right - left; // 거리

    area = width * Math.min(height[left], height[right]);
    maxArea = Math.max(area, maxArea);

    if (height[left] < height[right]) {. // -------------------> 변경
      // 더 낮은 벽을 이동해야 더큰 면적기대
      left++;
    } else {
      right--;
    } 
  }
  return maxArea;
};

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));