[LeetCode] : 1605. Find Valid Matrix Given Row and Column Sums

https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/description/

leetcode - Find Valid Matrix Given Row and Column Sums

문제 유형 : 그리디, 행렬

문제 난이도 : Medium

 

문제

You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the ith row and colSum[j] is the sum of the elements of the jth column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.

Find any matrix of non-negative integers of size rowSum.length x colSum.length that satisfies the rowSum and colSum requirements.

Return a 2D array representing any matrix that fulfills the requirements. It's guaranteed that at least one matrix that fulfills the requirements exists.

 

각 행의 합이 담긴 rowSum과 각 열의 합이 담긴 colSum이 주어진다.

이 정보를 이용하여 행렬을 복원하시오.

조건만 만족한다면 승인됩니다.

 

풀이

https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/solutions/5503406/greedy-matrix-with-2-pointers-23ms-beats-99-32/

위 풀이의 도움을 받음

 

행렬을 0으로 초기화한다. i = 0, j = 0부터 시작해서, rowSum[i]와 colSum[j]의 최소값을 matrix[i][j]에 입력한다. 그러고 그 최소값을 각 rowSum[i]와 colSum[j]에 뺀다. 그 값이 0이 된 경우에만, i, j가 각각 다음 인덱스로 향할 수 있다.

 

즉, 왼쪽 위부터 순차적으로 rowSum[i], colSum[j]의 최소값을 채우고, 그 행 또는 열의 합을 비우면 각각 다음 행, 열로 나아가서 수를 채운다.

나머지는 0으로 남아있는다. 

 

코드

C++

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        int r = rowSum.size();
        int c = colSum.size();
        vector<vector<int>> mat(r, vector<int>(c, 0));

        for(int i = 0, j = 0; i < r && j < c; i += (rowSum[i] == 0), j += (colSum[j] == 0)) {
            int x = min(rowSum[i], colSum[j]);
            mat[i][j] = x;
            rowSum[i] -= x;
            colSum[j] -= x;
        }
        return mat;
    }
};