🧱 초보자용 가이드 ‘그리드에서 정사각형 구멍의 면적 최대화’ – LeetCode 2943 (C++, Python, JavaScript)

Source: Dev.to

번역할 텍스트가 제공되지 않았습니다. 번역이 필요한 본문을 알려주시면 한국어로 번역해 드리겠습니다.

문제 개요

주어진 내용:

• 두 정수 n와 m은 격자에서 내부 가로 막대와 세로 막대의 개수입니다.
• 두 배열 hBars와 vBars는 제거할 수 있는 특정 막대들을 나열합니다.

격자는 막대로 구분된 셀들로 이루어져 있습니다. 연속된 막대를 제거하면 남아 있는 고정 막대 사이의 공간이 합쳐집니다.

• 막대 하나를 제거하면 2 단위의 틈이 생깁니다.
• 연속된 k개의 막대를 제거하면 k + 1 단위의 틈이 생깁니다.

목표는 제거 가능한 막대를 任意(어떤) 개수만큼 제거했을 때 만들 수 있는 정사각형 구멍의 최대 면적을 찾는 것입니다.

핵심 통찰

문제는 두 개의 독립적인 1‑D 하위 문제로 나눌 수 있다:

1. 수평 방향 – 연속적으로 제거 가능한 수평 막대의 가장 긴 연속 구간을 찾는다.
2. 수직 방향 – 연속적으로 제거 가능한 수직 막대의 가장 긴 연속 구간을 찾는다.

가장 긴 수평 연속 구간의 길이가 h이면, 최대 수평 간격은 h + 1이다.
마찬가지로, 길이가 v인 수직 연속 구간은 수직 간격 v + 1을 만든다.

구멍은 정사각형이어야 하므로, 변의 길이는 두 간격 중 더 작은 값에 의해 제한된다:

side = min(maxHorizontalGap, maxVerticalGap)
area = side * side

Source: …

알고리즘

1. 각 배열(hBars, vBars)을 정렬한다.
2. 정렬된 배열을 한 번 스캔하여 연속된 숫자의 가장 긴 연속 구간 길이를 계산한다.
3. 해당 방향의 최대 간격으로 longestRun + 1을 반환한다.
4. 두 간격 중 최소값을 변의 길이로 정하고, 이를 제곱한다.

의사코드

function getMaxGap(bars):
    sort(bars)
    maxRun = 1
    curRun = 1
    for i from 1 to bars.length-1:
        if bars[i] == bars[i-1] + 1:
            curRun += 1
        else:
            curRun = 1
        maxRun = max(maxRun, curRun)
    return maxRun + 1   // gap width

function maximizeSquareHoleArea(n, m, hBars, vBars):
    side = min(getMaxGap(hBars), getMaxGap(vBars))
    return side * side

복잡도 분석

• 각 배열 정렬: O(k log k) 여기서 k는 배열의 크기입니다.
• 선형 스캔: O(k).

전체 시간 복잡도: O(n log n + m log m).
공간 복잡도: O(1) 추가 (제자리 정렬).

참고 구현

C++

class Solution {
public:
    int maximizeSquareHoleArea(int n, int m, std::vector<int>& hBars, std::vector<int>& vBars) {
        int side = std::min(getMaxGap(hBars), getMaxGap(vBars));
        return side * side;
    }

private:
    int getMaxGap(std::vector<int>& bars) {
        if (bars.empty()) return 1;          // no removable bars → gap of 1
        std::sort(bars.begin(), bars.end());

        int max_consecutive = 1;
        int current_consecutive = 1;

        for (size_t i = 1; i < bars.size(); ++i) {
            if (bars[i] == bars[i-1] + 1) {
                ++current_consecutive;
            } else {
                current_consecutive = 1;
            }
            max_consecutive = std::max(max_consecutive, current_consecutive);
        }
        return max_consecutive + 1;
    }
};

Python

def get_max_gap(bars: list[int]) -> int:
    if not bars:
        return 1
    bars.sort()
    max_consecutive = 1
    cur = 1
    for i in range(1, len(bars)):
        if bars[i] == bars[i - 1] + 1:
            cur += 1
        else:
            cur = 1
        max_consecutive = max(max_consecutive, cur)
    return max_consecutive + 1

def maximizeSquareHoleArea(n: int, m: int, hBars: list[int], vBars: list[int]) -> int:
    side = min(get_max_gap(hBars), get_max_gap(vBars))
    return side * side

JavaScript

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} hBars
 * @param {number[]} vBars
 * @return {number}
 */
var maximizeSquareHoleArea = function (n, m, hBars, vBars) {
    const getMaxGap = (bars) => {
        if (bars.length === 0) return 1;
        bars.sort((a, b) => a - b);
        let maxConsecutive = 1;
        let cur = 1;
        for (let i = 1; i < bars.length; i++) {
            if (bars[i] === bars[i - 1] + 1) {
                cur++;
            } else {
                cur = 1;
            }
            maxConsecutive = Math.max(maxConsecutive, cur);
        }
        return maxConsecutive + 1;
    };

    const side = Math.min(getMaxGap(hBars), getMaxGap(vBars));
    return side * side;
};

추가 설명

• 연속성을 위한 정렬: 정렬은 문제를 단일 선형 패스로 축소시켜 전체적으로 O(k log k) 시간 복잡도를 제공합니다.
• 펜스포스트 고려: k개의 막대가 k + 1개의 공간을 구분합니다; 이를 제거하면 그 공간들이 하나로 합쳐집니다.
• 병목 원칙: 정사각형 형태의 제약에서는 더 작은 차원이 최종 크기를 결정합니다.

이 접근법은 2‑D 격자 문제를 두 개의 간단한 1‑D 스캔으로 변환하며, 자원 할당, 윈도우 관리 및 기타 실제 엔지니어링 시나리오에서 자주 유용한 기법입니다.