넘치게 채우기
[LeetCode] : 1605. Find Valid Matrix Given Row and Column Sums 본문
[LeetCode] : 1605. Find Valid Matrix Given Row and Column Sums
riveroverflow 2024. 7. 20. 10:11https://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이 주어진다.
이 정보를 이용하여 행렬을 복원하시오.
조건만 만족한다면 승인됩니다.
풀이
위 풀이의 도움을 받음
행렬을 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;
}
};
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 2418. Sort the People (0) | 2024.07.22 |
---|---|
[LeetCode] 2392. Build a Matrix With Conditions (0) | 2024.07.21 |
[LeetCode] 1380. Lucky Numbers in a Matrix (0) | 2024.07.19 |
[LeetCode] 1530. Number of Good Leaf Nodes Pairs (0) | 2024.07.18 |
[LeetCode] 1110. Delete Nodes And Return Forest (0) | 2024.07.17 |