[LeetCode] 1074. Number of Submatrices That Sum to Target

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description/?envType=daily-question&envId=2024-01-28

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Number of Submatrices That Sum to Target

문제 유형 : 부분합, 투 포인터

문제 난이도 : Hard

 

문제

Given a matrix and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

 

행렬과 target이 주어진다.

부분행렬의 합이 target을 만족하는 개수를 구하시오.

 

 

풀이

우선, matrix를 순회하면서, 각 행들별로 오른쪽 열로 가면서 합을 누적시켜놓는다.

이러면 matrix[i][j]는 matrix[i][0]부터 matrix[i][j]까지의 합이 된다.

기존 값을 구하고 싶으면, 이번 열의 부분합을 빼는 식으로 하면 된다.

 

이제 두 열 인덱스에 대한 포인터 c1, c2를 만든다.

그리고 해시 맵을 만든 뒤, 각 열을 확장해가면서 sum-개수의 쌍을 저장시킨다.

 

 

for (c1 = 0; c1 < n; c1++) {

    for(c2 = c1; c2 < n; c2++) {

        map선언 및 sum 초기화

        for(r = 0; r < m; r++) {

            (누적 합 구한 뒤, map에 저장하고 count를 누적시킴)

        }

    }

}

 

코드

C++

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        const int m = matrix.size();
        const int n = matrix[0].size();
        int count = 0;

        for(int i = 0; i < m; i++) {
            for(int j = 1; j < n; j++) {
                matrix[i][j] += matrix[i][j-1];
            }
        }

        for(int c1 = 0; c1 < n; c1++) {
            for(int c2 = c1; c2 < n; c2++) {
                unordered_map<int, int> mp;
                mp[0] = 1;
                int sum = 0;

                for(int r = 0; r < m; r++) {
                    sum += matrix[r][c2] - (c1>0?matrix[r][c1-1]:0);
                    count += mp[sum-target];
                    mp[sum]++;
                }
            }
        }

        return count;
    }
};