꒰ྀི 13. LeetCode:: 행과 열의 합이 주어진 유효한 행렬 찾기

주어진 rowSum과 colSum을 만족하는 행렬을 구성한다.
각 행과 열의 합이 주어진 값을 만족하는 동시에, 음이 아닌 정수여야 한다.

 

이 문제를 해결하기 위해 탐욕법을 사용했다.

각 셀에 가능한 최댓값을 할당하며 rowSum과 colSum을 줄여나간다.

1. rowSum과 colSum의 크기에 맞는 행렬 초기화
2. 각 셀에 최댓값을 할당하며 줄여나감
3. 모든 rowSum과 colSum이 0이 될 때까지 반복함

 

function restoreMatrix(rowSum, colSum) {
    const numRows = rowSum.length;
    const numCols = colSum.length;
    const matrix = Array.from({ length: numRows }, () => Array(numCols).fill(0));

    let i = 0, j = 0;

    while (i < numRows && j < numCols) {
        const minValue = Math.min(rowSum[i], colSum[j]);
        matrix[i][j] = minValue;
        rowSum[i] -= minValue;
        colSum[j] -= minValue;

        if (rowSum[i] === 0) {
            i++;
        }
        if (colSum[j] === 0) {
            j++;
        }
    }

    return matrix;
}

1. 행렬의 크기를 초기화함
2. 두 포인터 i와 j를 이용해 행과 열을 가리키게함
3. 할당된 값을 rowSum[i]와 colSum[j]에서 빼줌
4. rowSum과 colSum이 0이 될 때까지 반복함