Software Enginner πŸ‡―πŸ‡΅ and πŸ‡°πŸ‡·

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

Problem Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Difficulty Medium
Language Java
Time complexity $$O(n + \log_n + m + \log_m)$$
Space complexity $$O(1)$$


You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut. Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.



였늘 λ³Έ μ½”λ”© ν…ŒμŠ€νŠΈμ—μ„œ λ‚˜μ˜¨ 문제인데, 이야 이걸 λͺ»ν’€μ—ˆλ‹€λŠ”κ²Œ μ°Έ λ©μ²­ν–ˆλ‹€. μš°μ„ , hc 와 vc κ°€ μ •λ ¬λ˜μ–΄ μžˆλ‹€λŠ” κ°€μ • ν•˜μ— (μ•ˆλ˜μ–΄ μžˆμ„ 수 μžˆμœΌλ‹ˆ μ •λ ¬ λ•Œλ¦¬κ³ ) μ‹œμž‘ν•œλ‹€.

μ‚¬λžŒμ€ νƒœμ–΄λ‚˜ μ„œμšΈλ‘œ 보내라 ν•˜λ˜κ°€. μ–˜λ„ κ²°κ΅­ 핡심은 ν•˜λ‚˜λ‹€. λͺ¨λ“  경우의 수λ₯Ό λ‹€ 탐색할 μ΄μœ κ°€ μ—†λ‹€.

  1. λ‚΄κ°€ 이 μΌ€μžŒμ˜ 끝을 μ•ˆλ‹€
  2. μž˜λ¦¬λŠ” λ²”μœ„λ₯Ό μ•ˆλ‹€

즉, μ΅œλŒ€λ‘œ 자λ₯Ό 수 μžˆλŠ” λ²”μœ„λ₯Ό μš°μ„  κ΅¬ν•œλ‹€. 그리고 λ‚΄κ°€ 자λ₯Έ 것보닀 λ‚¨μ€κ²Œ 더 크면 그게 μ΅œλŒ€ 값일 것이닀.

import java.util.*;
import java.math.*;

class Solution {
    public int maxArea(int h, int w, int[] hc, int[] vc) {
        int curHeight = 0;
        long maxHeight = 0;
        for (int i = 0; i < hc.length; ++i) {
            maxHeight = Math.max(hc[i] - curHeight, maxHeight);
            curHeight = hc[i];
        int curWidth = 0;
        long maxWidth = 0;
        for (int i = 0; i < vc.length; ++i) {
            maxWidth = Math.max(vc[i] - curWidth, maxWidth);
            curWidth = vc[i];
        maxWidth = Math.max(maxWidth, w - vc[vc.length - 1]);
        maxHeight = Math.max(maxHeight, h - hc[hc.length - 1]);
        long result = maxHeight * maxWidth;
        return (int) ((maxHeight * maxWidth) % 1000000007);

μ‹œκ°„ λ³΅μž‘λ„λŠ” O(n + log n + m + log m) 정도 κ°™λ‹€.

μ§‘μ—μ„œ 10뢄에 ν‘Όκ±Έ λͺ»ν‘Έλ„€.. μ‚Άμ΄λž€ μ°Έ κΈ°κ΅¬ν•œ 법이닀..