🔲 초보자용 가이드 ‘Maximum Side Length of a Square’ – LeetCode 1292 (C++, Python, JavaScript)

Source: Dev.to

문제 요약

주어지는 것

• mat 라는 이름의 정수 2‑D 행렬.
• threshold 라는 정수.

목표

요소들의 합이 ≤ threshold 인 정사각형 부분 행렬 중 최대 변의 길이를 반환합니다.
그러한 정사각형이 없으면 0을 반환합니다.

단계별 안내: 예제 이해

예제 1

입력

mat = [
  [1,1,3,2,4,3,2],
  [1,1,3,2,4,3,2],
  [1,1,3,2,4,3,2]
]
threshold = 4

• 변의 길이 1 → 단일 1이면 충분합니다.
• 변의 길이 2 → 좌상단 정사각형 [[1,1],[1,1]]의 합이 4이며 → 유효합니다.
• 변의 길이 3 → 가장 작은 3×3 정사각형의 합이 이미 4를 초과합니다.

출력

2

예제 2

입력

mat = [
  [2,2,2,2,2],
  [2,2,2,2,2],
  ...
]
threshold = 1

모든 요소가 2이므로 1×1 정사각형조차도 임계값을 초과합니다.

출력

0

Intuition

이 문제를 효율적으로 풀기 위해 두 가지 강력한 기법을 결합합니다:

1. 2‑D Prefix Sums – 행렬을 미리 처리해 어떤 정사각형의 합도 O(1) 시간에 구할 수 있게 합니다.
2. Binary Search on the answer – 정사각형의 변 길이는 단조성을 가집니다: 크기 k인 정사각형이 조건을 만족하면, 더 작은 크기의 정사각형도 모두 만족합니다. 이를 이용해 최대 가능한 k를 O(log min(m,n)) 시간에 찾을 수 있습니다.

1️⃣ 2‑D Prefix Sum

preSum[i][j]는 좌상단 코너 (0,0)부터 (i‑1, j‑1)까지 (포함) 사각형의 합을 저장합니다.

변 길이가 len이고 오른쪽 아래 코너가 (i, j)인 정사각형의 합은 다음과 같습니다:

sum = preSum[i][j]
      - preSum[i‑len][j]
      - preSum[i][j‑len]
      + preSum[i‑len][j‑len]

preSum 테이블의 모든 인덱스는 1‑기반이므로 위 식은 O(1) 에 동작합니다.

2️⃣ Binary Search on Answer

• Low = 0, High = min(rows, cols).
• low ≤ high 인 동안 반복:
  • mid = (low + high) // 2.
  • prefix sum을 이용해 mid × mid 정사각형 중 합이 ≤ threshold 인 것이 있는지 확인합니다.
  • 발견되면 mid를 후보로 기록하고 더 큰 크기를 탐색합니다 (low = mid + 1).
  • 그렇지 않으면 더 작은 크기를 탐색합니다 (high = mid - 1).

전체 복잡도는 O(m·n + m·n·log min(m,n)) 로, prefix‑sum 구축과 binary‑search 검사가 지배합니다.

코드 블록

C++ (부분)

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));

        // Build 2‑D Prefix Sum
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                preSum[i][j] = mat[i-1][j-1] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
            }
        }
        // ... (rest of the algorithm)
    }
};

Python (부분)

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])
        preSum = [[0] * (n + 1) for _ in range(m + 1)]

        # Build 2‑D Prefix Sum
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                preSum[i][j] = (mat[i - 1][j - 1] +
                                preSum[i - 1][j] +
                                preSum[i][j - 1] -
                                preSum[i - 1][j - 1])

        def check(k: int) -> bool:
            if k == 0:
                return True
            for i in range(k, m + 1):
                for j in range(k, n + 1):
                    cur = (preSum[i][j] -
                           preSum[i - k][j] -
                           preSum[i][j - k] +
                           preSum[i - k][j - k])
                    if cur <= threshold:
                        return True
            return False

        # Binary search omitted for brevity

JavaScript (부분)

var maxSideLength = function(mat, threshold) {
    const m = mat.length, n = mat[0].length;
    const preSum = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    // Build 2‑D Prefix Sum
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            preSum[i][j] = mat[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
        }
    }

    const canFit = (k) => {
        if (k === 0) return true;
        for (let i = k; i <= m; ++i) {
            for (let j = k; j <= n; ++j) {
                const cur = preSum[i][j] - preSum[i - k][j] - preSum[i][j - k] + preSum[i - k][j - k];
                if (cur <= threshold) return true;
            }
        }
        return false;
    };

    // Binary search omitted for brevity
};

정리된 JavaScript 구현

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        preSum[i][j] = mat[i - 1][j - 1] + preSum[i - 1][j] + 
                       preSum[i][j - 1] - preSum[i - 1][j - 1];
    }
}

let low = 0;
let high = Math.min(m, n);
let ans = 0;

while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (mid === 0) {
        low = mid + 1;
        continue;
    }

    let found = false;
    for (let i = mid; i <= m; i++) {
        for (let j = mid; j <= n; j++) {
            let currentSum = preSum[i][j] - preSum[i - mid][j] -
                             preSum[i][j - mid] + preSum[i - mid][j - mid];
            if (currentSum <= threshold) {
                found = true;
                break;
            }
        }
        if (found) break;
    }

    if (found) {
        ans = mid;
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
return ans;

주요 내용

• 2D Prefix Sums: 이 기법은 전처리 후 영역 합 쿼리를 *O(k²)*에서 O(1) 로 감소시킵니다. 격자 기반 문제에서 반드시 알아야 합니다.
• Binary Search on Results: 조건을 만족하는 “최대” 또는 “최소” 값을 찾아야 할 때, 탐색 공간이 정렬되어 있는지 확인하고 이진 탐색을 적용하세요.
• Inclusion‑Exclusion Principle: 접두합 및 영역 합 공식은 이 원리를 직접 적용한 것으로, 겹치는 영역을 중복 계산하지 않도록 보장합니다.

최종 생각

이 문제는 두 개의 비교적 단순한 개념을 결합하면 매우 최적화된 솔루션을 얻을 수 있다는 훌륭한 예시입니다. 실제 세계에서는 이러한 유형의 공간 쿼리가 Computer Vision에서 객체 탐지에, 그리고 **Geographic Information Systems (GIS)**에서 특정 지도 영역 내 데이터 밀도를 분석하는 데 사용됩니다. 2D prefix sum을 마스터하면 행렬 조작과 관련된 모든 인터뷰에서 큰 이점을 얻을 수 있습니다.