1074. Number of Submatrices That Sum to Target

• m x n 행렬이 주어졌을 때 부분 행렬 원소의 합이 주어진 숫자 target이 되는 경우의 수를 구하는 문제.
• 행렬의 최대 크기는 100 x 100 이다.

• 단순하게 모든 경우의 수를 시도해보는 경우 시간 복잡도는 이 된다.
• 먼저 모든 부분 행렬의 경우의 수는 m == n 임을 가정했을 때 이다.
• 행렬의 행 시작 점, 끝점, 열 시작점, 끝점 각각을 모두 시도해보아야 한다.
• 더불어 각 부분 행렬에 대해서 모든 원소를 더하는 것은 의 시간 복잡도를 가진다.
• 이므로 예상 실행 시간은 가량이 되므로 시간 초과가 된다 (k는 로직을 1회 실행하는 시간).

• 이를 줄이기 위해 prefixed sum을 활용한다.
• 행렬의 각 행에 대하여 첫번째 열 부터 마지막 열 까지 누적된 합을 미리 계산하여 2d 배열 pSum에 저장한다.
• 단, 계산의 편의를 위해서 열의 개수 + 1 n + 1 만큼 공간을 잡고 1 번쨰 열 부터 값을 저장한다.
• 이렇게 하면 [a, b] 열 범위의 값을 구할 때 pSum[b + 1] - pSum[a]와 같이 구할 수 있다.
• 열 범위의 값을 더하는 시간 복잡도를 에서 로 감소시킬 수 있다.

• 모든 부분 행렬의 경우의 수에 대해서 원소의 합을 구하고 그 값이 주어진 숫자 target와 동일한 경우의 수를 센다.
• 부분 행렬의 행 범위 [si, ei], 열 범위 [sj, ej]에 대해서 원소의 합을 미리 계산된 prefixed sum 배열을 이용하여 구한다 → .
• 루프 순서를 바꿔서 각 행 별 prefixed sum을 더하는 루프와 부분 행렬의 경우의 수를 탐색하는 루프를 통합한다 → .
• 최종적으로 시간 복잡도는 가 된다.

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int result = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] pSum = new int[m][n + 1];
        for (int i = 0; i < m; ++i) {
            for (int j = 1; j <= n; ++j) {
                pSum[i][j] = pSum[i][j - 1] + matrix[i][j - 1];
            }
        }
        for (int sj = 0; sj < n; ++sj) { // 열의 시작점
            for (int ej = sj; ej < n; ++ej) { // 열의 끝점
                for (int si = 0; si < m; ++si) { // 행의 시작점
                    int sum = 0;
                    for (int ei = si; ei < m; ++ei) { // 행의 끝점
                        sum += pSum[ei][ej + 1] - pSum[ei][sj];
                        if (target == sum) ++result;
                    }
                }
            }
        }
        return result;
    }
}

• 루프 순서를 바꾸지 않으면 아래와 같이 되는데 마지막에 행 별로 prefixed sum을 더하는 부분 때문에 시간 복잡도가 가 되서 시간 초과가 된다.
• (2), (5) 번 루프는 똑같이 행 범위를 따라 움직이므로 이를 통합하여 원소의 합을 계산하는 부분을 단순화할 수 있다.

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        ... omitted ...
        for (int si = 0; si < m; ++si) { // (1) 행의 시작점
            for (int ei = si; ei < m; ++ei) { // (2) 행의 끝점: si ~ ei를 따라서 순회
                for (int sj = 0; sj < n; ++sj) { // (3) 열의 시작점
                    for (int ej = sj; ej < n; ++ej) { // (4) 열의 끝점
                        int sum = 0;
                        for (int i = si; i <= ei; ++i) { // (5) si ~ ei까지 순회
                            sum += pSum[i][ej + 1] - pSum[i][sj];
                        }
                        if (target == sum) {
                            ++result;
                        }
                    }
                }
            }
        }
        return result;
    }
}