๋ฌธ์ ๋งํฌ
Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
์ ์ฒด ๋์ด(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)
};
'์ฝ๋ฉํ ์คํธ > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] Longest Consecutive Sequence (0) | 2022.07.05 |
---|---|
[LeetCode] Candy (0) | 2022.07.04 |
[LeetCode] Maximum Bags With Full Capacity Of Rocks (0) | 2022.07.02 |
[LeetCode] Maximum Units On A Truck (0) | 2022.07.01 |
[LeetCode] Minimum Deletions To Make Character Frequencies Unique (0) | 2022.06.28 |