[LeetCode] Maximum Area Of A Piece Of Cake After Horizontal And Vertical Cuts

문제링크

Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts - LeetCode

 

전체 높이(h), 폭(w)이 주어지고
수평으로 자르는 부분(horizontalCuts), 수직으로 자르는 부분(verticalCuts)가 주어진다.

이때 잘려진 부분 중 최대 값을 구하라.

접근 방법

만약 h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3] 라면
실제 나뉘는 부분은 horizontalCuts = [0,1,2,4,5], verticalCuts = [0,1,3,4]이 된다.

따라서 실제 나뉘는 부분으로 새로운 배열을 만들고 정렬 해준다.

const newHorizontalCuts = [0, ...horizontalCuts, h].sort((a,b) => a - b);
const newVerticalCuts = [0, ...verticalCuts, w].sort((a,b) => a - b);​

 

그리고 잘리는 선을 기준으로 나뉜 부분의 크기를 구해준다.

const cuttedHLen = [];
const cuttedWLen = [];

for(let i = 1; i < newHorizontalCuts.length; i++){
    cuttedHLen.push(newHorizontalCuts[i] - newHorizontalCuts[i-1]);
}
for(let i = 1; i < newVerticalCuts.length; i++){
    cuttedWLen.push(newVerticalCuts[i] - newVerticalCuts[i-1]);
}​

마지막으로 나뉜 가로와 세로의 길이의 최대값을 가져와 서로 곱해준다.

let maxArea = BigInt(Math.max(...cuttedHLen)) * BigInt(Math.max(...cuttedWLen));
    
return maxArea % BigInt(1e9 + 7)​

배운점

매우 큰수가 나올 경우 10^9 + 7로 나눈 나머지를 정답으로 구하라는 조건이 있었다.

하지만 BigInt를 사용하지 않으면 정답을 구할 수 없었다.

let maxArea = Math.max(...cuttedHLen) * Math.max(...cuttedWLen);
    
return maxArea % (1e9 + 7)​

실제 개발자도구에서 확인해 본 결과 BigInt를 사용하지 않으면 1의 자리의 4를 구하지 못하는 것을 확인할 수 있다.

MDN에서 BigInt에 대해 알아보니 2^53 - 1 이상의 수를 다룰 경우 BigInt를 사용하길 권장한다.

2^53 - 1 ~= 1e15 * 9

※ BigInt를 계산할때엔 BigInt끼리만 계산할 수 있다. ( BigInt(2) * 2 안됨 )

 

/**
 * @param {number} h
 * @param {number} w
 * @param {number[]} horizontalCuts
 * @param {number[]} verticalCuts
 * @return {number}
 */
 var maxArea = function(h, w, horizontalCuts, verticalCuts) {
  const newHorizontalCuts = [0, ...horizontalCuts, h].sort((a,b) => a - b);
  const newVerticalCuts = [0, ...verticalCuts, w].sort((a,b) => a - b);
  
  const cuttedHLen = [];
  const cuttedWLen = [];
  
  for(let i = 1; i < newHorizontalCuts.length; i++){
      cuttedHLen.push(newHorizontalCuts[i] - newHorizontalCuts[i-1]);
  }
  for(let i = 1; i < newVerticalCuts.length; i++){
      cuttedWLen.push(newVerticalCuts[i] - newVerticalCuts[i-1]);
  }
  
  let maxArea = BigInt(Math.max(...cuttedHLen)) * BigInt(Math.max(...cuttedWLen));
  
  return maxArea % BigInt(1e9 + 7)
};