Post

[LeetCode] #73 - Set Matrix Zeroes [Java][C++][Python]

[LeetCode] #73 - Set Matrix Zeroes [Java][C++][Python]

문제 링크


1. 아이디어

0이 있는 칸의 행과 열을 모두 0으로 만드는 문제이다. 0을 발견하자마자 바꾸면 새로 생긴 0을 원래 있던 0과 구분할 수 없어 다른 행과 열로 번지므로, 먼저 0이 있는 행과 열을 표시해 두고 나중에 한꺼번에 바꾼다. 행마다 하나, 열마다 하나씩 표시를 두면 보조 공간은 $O(m + n)$이다.

지문의 Follow-up은 보조 공간을 상수로 줄이는 것을 묻고, 첫 행·열 재사용이 그것에 맞춘 풀이이다. 별도 배열 대신 첫 행의 칸을 그 열의 표시로, 첫 열의 칸을 그 행의 표시로 쓴다. 첫 행의 칸에 원래 있던 0은 그 열이 어차피 0이 되어야 한다는 뜻이고 첫 열도 마찬가지라, 표시로 읽혀도 결과가 같다. 다만 첫 행과 첫 열 자체에 0이 있었는지는 표시가 덮어써 사라지므로 표시하기 전에 기억해 둔다.

첫 행과 첫 열은 안쪽 칸을 모두 바꾼 뒤 마지막에 처리한다. 먼저 0으로 바꾸면 표시 칸이 전부 0이 되어 표시가 없던 안쪽 칸까지 0이 되기 때문이다.

4×5 행렬 [[1,1,1,0,1],[1,0,1,1,1],[1,1,1,1,1],[1,1,0,1,1]]에서 첫 행·열을 표시로 재사용해 [[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,1],[0,0,0,0,0]]이 되는 과정 4×5 행렬 [[1,1,1,0,1],[1,0,1,1,1],[1,1,1,1,1],[1,1,0,1,1]]에서 첫 행·열을 표시로 재사용해 [[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,1],[0,0,0,0,0]]이 되는 과정


2. 코드

풀이 1: 행·열 표시 배열 [Java][C++][Python]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) matrix[i][j] = 0;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> row(m);
        vector<bool> col(n);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) matrix[i][j] = 0;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        row = [False] * m
        col = [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = True
                    col[j] = True

        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0

풀이 2: 첫 행·열 재사용 [Java][C++][Python]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowHas0 = false, firstColHas0 = false;

        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColHas0 = true;
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowHas0 = true;
        }

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

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

        if (firstColHas0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (firstRowHas0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool first_row_has_0 = false, first_col_has_0 = false;

        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) first_col_has_0 = true;
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) first_row_has_0 = true;
        }

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

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

        if (first_col_has_0) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
        if (first_row_has_0) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_has_0, first_col_has_0 = False, False

        for i in range(m):
            if matrix[i][0] == 0:
                first_col_has_0 = True
        for j in range(n):
            if matrix[0][j] == 0:
                first_row_has_0 = True

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        if first_col_has_0:
            for i in range(m):
                matrix[i][0] = 0
        if first_row_has_0:
            for j in range(n):
                matrix[0][j] = 0

This post is licensed under CC BY 4.0 by the author.