Set Matrix Zeroes

💬 문제

[문제 링크]

m * n의 정수 배열 matrix
0이 있는 곳의 행, 열의 값을 모두 0으로 변경
in-place 알고리즘으로 진행하여 반환값 없음

✍️ 나의 풀이

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    let row = new Set();
    let col = new Set();

    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] === 0) {
                row.add(i);
                col.add(j);
            }
        }
    }

    row.forEach((idx) => {
        for (let i = 0; i < matrix[0].length; i++)
            matrix[idx][i] = 0;
    });
    col.forEach((idx) => {
        for (let i = 0; i < matrix.length; i++)
            matrix[i][idx] = 0;
    });
};

배열을 순회하면서 0을 만나면 해당 위치의 행, 열 인덱스를 각각 row, col set에 저장
이후 set에 저장된 값에 따라 행과 열에 위치한 모든 인덱스 값을 0으로 변경

📌 결과

Accepted
Runtime 69ms (Beats 86.83%)
Memory 53.52MB (Beats 33.79%)

📚 러닝 포인트

이번에도 in-place로 진행하라고 했는데, 일단 set 두개를 사용했다. 그래서 위키를 다시 읽어보니까 엄청 엄격하게 제한했을 때만 추가 메모리를(인덱스 접근하는 것 빼고) 안쓰는 것이지 보통은 입력값의 크기만한 공간을 사용하지 않으면 되는 거라고 한다. 그래서 0이 위치한 곳의 행, 열 값 중복을 없애기 위하여 set를 사용하였고 순회를 위해서 forEach를 썼다. 어떤 사람들은 matrix를 다시 돌면서 지금 인덱스가 set에 들어있으면 0으로 바꾸고 아니면 넘기는 식으로 구현하기도 했더라. 그리고 문제 마지막 부분에서 공간 복잡도를 O(1)으로 할 수 있는 방법을 찾아보라고 했는데, 일단 나는 O(m+n)으로 구현했다. 처음에는 그럴 수 있는 방법을 열심히 생각했으나 실패해서 찾아보니까 0을 만나면 즉시 해당 위치의 행과 열의 값을 바꾸는 대신 원래 0이었던 곳은 구별을 해야하므로 null이나 문자열 같은것으로 바꿔둔 뒤에 마지막에 한 번에 0으로 변경하는 방법이 있었다.