[Leetcode] 73. Set Matrix Zeroes - JS

https://leetcode.com/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
- m x n 정수 행렬 matrix가 주어진다.
- 요소가 0인 위치의 행, 열의 다른 요소들도 0으로 제자리에서 변경하라.

제한조건
--------------------
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1

 

2. 접근 방법

접근방법
--------------------
0의 (i, j) 좌표를 알아내어, matrix[i][~] = 0 matrix[~][j] = 0 으로 바꿔준다.
0이 여러 개 일수 있는데, 0의 i 좌표 리스트, j 좌표 리스트를 추가하여 각 요소마다 확인하여 바꿔준다.

 

 

3. 코드

var setZeroes = function(matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    let zeroI = [];
    let zeroJ = [];

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                zeroI.push(i);
                zeroJ.push(j);
            }
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (zeroI.includes(i) || zeroJ.includes(j)) {
                matrix[i][j] = 0
            }
        }
    }
};

 

 

 

4. 복잡도 분석

- 시간복잡도: O(n * m)

- 공간복잡도: O(n + m)

 

push, includes 메서드를 사용하는 것 대신 zeroI 배열을 row 길이만큼 0으로 초기화하고, zeroJ 배열을 col 길이만큼 0으로 초기화 한다. 그리고 matrix[i][j] === 0 을 만족하면 zeroI[i] = 1, zeroJ[j] = 1을 각각 할당하고 두번째 순회 때 includes 대신 zeroI[i] === 1 || zeroJ[j] === 1 만족하면 해당 요소를 0으로 바꿔주는 방법도 있다.

 

코드

var setZeroes = function(matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    let zeroI = Array.from({length:m}, () => 0);
    let zeroJ = Array.from({length:n}, () => 0);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                zeroI[i] = 1;
                zeroJ[j] = 1;
            }
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (zeroI[i] === 1 || zeroJ[j] === 1) {
                matrix[i][j] = 0
            }
        }
    }
};