Portfolio

📑 문제

아마존, 페이스북에서 많이 출제된 문제입니다

✏️ 풀이

재영

단순하게 풀었어요!

메인함수에서 결과를 미리 적어줘요! 결국 길이를 구하는 로직이 중복되니 함수로 호출합시다.

정렬되었다는 말은 없으니 정렬을 해주고

쭉 돌아가는데, 이전 것과 비교했을 때의 차이의 길이가 가장 긴 길이인지 확인해봅시다.

조건에 주어진 나머지를 적용하여 결과를 리턴해줍시다.


const getMaxLength = (size, cuts) => {
  let maxSize = 0;
  [0, ...cuts, size]
    .sort((a, b) => a - b)
    .forEach((nowValue, nowIdx, arr) => {
    if (!nowIdx) return;
    maxSize = Math.max(maxSize, nowValue - arr[nowIdx - 1])
  })

  return BigInt(maxSize);
}

const maxArea = (h, w, horizontalCuts, verticalCuts, modulo=BigInt(1000000007)) => {
  return getMaxLength(h, horizontalCuts) * getMaxLength(w, verticalCuts) % modulo
};

// 148 ms, faster than 33.47%

효성

첫 번째 풀이


var maxArea = function(h, w, horizontalCuts, verticalCuts) {
    const modulo = BigInt(1000000007)
    let maxHeight = 0;
    let maxWidth = 0;
    
    horizontalCuts.sort((a,b) => a-b)
    verticalCuts.sort((a,b) => a-b)
    
    for(let i=0; i<horizontalCuts.length-1; i++){
        let diff = horizontalCuts[i+1] - horizontalCuts[i];
        if(maxHeight < diff) {
            maxHeight = diff;
        }
    }
    for(let i=0; i<verticalCuts.length-1; i++) {
        let diff = verticalCuts[i+1] - verticalCuts[i];
        if(maxWidth < diff) {
            maxWidth = diff;
        }
    }
    const horizontalToptoMargin = horizontalCuts[0] - 0;
    const horizontalBottomtoMargin = h - horizontalCuts[horizontalCuts.length -1];
    const maxHorizontal = horizontalToptoMargin - horizontalBottomtoMargin > 0 ? horizontalToptoMargin : horizontalBottomtoMargin;
    
    const verticalToptoMargin = verticalCuts[0] - 0;
    const verticalBottomtoMargin = w - verticalCuts[verticalCuts.length -1];
    const maxVertical = verticalToptoMargin - verticalBottomtoMargin > 0 ? verticalToptoMargin : verticalBottomtoMargin;
    
    const finalHeight = maxHeight - maxHorizontal > 0 ? maxHeight : maxHorizontal;
    const finalWidth = maxWidth - maxVertical > 0 ? maxWidth : maxVertical;
    
    return BigInt(finalHeight) * BigInt(finalWidth) % modulo;
};

두 번째 풀이


var maxArea = function(h, w, horizontalCuts, verticalCuts) {
    const modulo = BigInt(1000000007)
    
    horizontalCuts.sort((a,b) => a-b);
    verticalCuts.sort((a,b) => a-b);
    
    let maxHeight = horizontalCuts[0];
    let maxWidth = verticalCuts[0];
    
    maxHeight = getMaxLength(horizontalCuts, maxHeight, h);
    maxWidth = getMaxLength(verticalCuts, maxWidth, w);
    
    return BigInt(maxHeight)*BigInt(maxWidth) % modulo;
    
};

function getMaxLength (arr, currDiff, length) {
    for(let i=0; i<arr.length-1; i++) {
        let compareDiff = arr[i+1] - arr[i];
        if(currDiff < compareDiff) {
            currDiff = compareDiff;
        }
    }    
    return currDiff < length - arr[arr.length-1] ? length - arr[arr.length-1] : currDiff;
}

💡

- 같은 패턴이 반복된다면 함수로 빼기. - sort는 원본 배열을 변경함. - 0에서 Cuts를 구하는 건 초기값으로 설정해도 괜찮음! - 간혹 큰 수의 결과가 나올 경우 modulo를 제안하는 경우가 있음을 명심하기!

은찬


/**
 * @param {number} h
 * @param {number} w
 * @param {number[]} horizontalCuts
 * @param {number[]} verticalCuts
 * @return {number}
 */
const getMaxDiff = (arr, start, end, diff, length) => {
    for(let i = 1; i < arr.length; i++){
        const tmpStart = arr[i - 1];
        const tmpEnd = arr[i];
        const tmpDiff = tmpEnd - tmpStart;
        
        diff = diff < tmpDiff ? tmpDiff : diff;
    }
    
    return diff < length - arr[arr.length - 1] ? length - arr[arr.length - 1] : diff;
};

const maxArea = (h, w, horizontalCuts, verticalCuts) => {
    const MOD = BigInt(1000000007);
    let rowDiff = 0;
    let colDiff = 0;
    
    horizontalCuts.sort((a, b) => a - b);
    verticalCuts.sort((a, b) => a - b);
    
    rowDiff = horizontalCuts[0];
    colDiff = verticalCuts[0];
    
    rowDiff = getMaxDiff(horizontalCuts, 0, rowDiff, rowDiff, h);
    colDiff = getMaxDiff(verticalCuts, 0, colDiff, colDiff, w);
    
    return (BigInt(rowDiff) * BigInt(colDiff)) % MOD;
};

현석

첫번째 풀이


var maxArea = function(h, w, horizontalCuts, verticalCuts) {
  
		horizontalCuts.sort((a,b) => a - b);
    verticalCuts.sort((a,b) => a - b)

    const lengths = horizontalCuts.map((el, index) => {
        if (index === 0) return el - 0;
        return el - horizontalCuts[index-1] 
    })
    
    lengths.push(h - horizontalCuts[horizontalCuts.length - 1])
    
    const widths = verticalCuts.map((el, index) => {
        if (index === 0) return el - 0;
        return el - verticalCuts[index-1] 
    })
    
    widths.push(w - verticalCuts[verticalCuts.length - 1])
    
    
    const maxLength = Math.max(...lengths);
    const maxWidth = Math.max(...widths)
    
    return BigInt(maxLength) * BigInt(maxWidth) % 1000000007n 
};

Runtime: 156 ms, faster than 26.29%
Memory Usage: 49.5 MB, less than 51.79%

가영


const maxArea = (h, w, horizontalCuts, verticalCuts) => { 
    const mod = 1e9 + 7;
    
    return findMaxLength(horizontalCuts, h) * findMaxLength(verticalCuts, w) % BigInt(mod);
};

const findMaxLength = (cutPoints, maxPoint) => {
    cutPoints.push(maxPoint);

    cutPoints.sort((a, b) => a - b);

    let maxLength = cutPoints[0];

    for (let i = 1; i < cutPoints.length; i++) {
        maxLength = Math.max(maxLength, cutPoints[i] - cutPoints[i - 1])
    }

    return BigInt(maxLength);
}

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

📑 문제

✏️ 풀이

첫 번째 풀이

두 번째 풀이