(Leetcode) 73 - Set Matrix Zeroes 풀이
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/set-matrix-zeroes/
Matrix(행렬) 문제다.
어려운 문제는 아니기 때문에 한번에 풀었고, 따로 코멘트 할 부분은 없을 것 같다.
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m = len(matrix)
n = len(matrix[0])
keep = []
for i, row in enumerate(matrix):
for j, cell in enumerate(row):
if cell == 0:
keep.append([i, j])
for zero in keep:
i, j = zero
for x in range(0, n):
matrix[i][x] = 0
for y in range(0, m):
matrix[y][j] = 0
자바로 다시 풀기 (24.07.31)
처음 생각난 방법
class Solution {
public void setZeroes(int[][] matrix) {
List<Index> indexOfZero = new ArrayList<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
indexOfZero.add(new Index(i, j));
}
}
}
for (Index index : indexOfZero) {
// update row
Arrays.fill(matrix[index.i], 0);
// update column
for (int i = 0; i < matrix.length; i++) {
matrix[i][index.j] = 0;
}
}
}
}
class Index {
int i;
int j;
public Index(int i, int j) {
this.i = i;
this.j = j;
}
}
TC, SC
문제에서 m과 n이 다음과 같이 정의되어 있다.
m == matrix.length
n == matrix[0].length
시간복잡도는 O(n * m) 공간복잡도는 O(n * m) 이다.
simple improvement O(n + m)
어떤 행과 열이 0으로 바뀔지만 기록해둔다면 이전보다 공간을 절약할 수 있다.
class Solution {
public void setZeroes(int[][] matrix) {
int[] row = new int[matrix.length];
int[] col = new int[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
col[j] = 1;
}
}
}
// update row
for (int i = 0; i < row.length; i++) {
if (row[i] == 1) {
Arrays.fill(matrix[i], 0);
}
}
// update column
for (int j = 0; j < col.length; j++) {
if (col[j] == 1) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][j] = 0;
}
}
}
}
}
TC, SC
문제에서 m과 n이 다음과 같이 정의되어 있다.
m == matrix.length
n == matrix[0].length
시간복잡도는 O(n * m) 공간복잡도는 O(n + m) 이다. 공간 복잡도가 개선되었다.
in place 방식
문제를 자세히 읽어보면 in place 방식으로 풀라고 되어있다. 추가적인 공간을 사용하면 안된다. 그래서 다음과 같이 바꿔보았다. 컨셉은 첫번째 풀이와 동일하다.
행렬의 값은 -231 <= matrix[i][j] <= 231 - 1 으로 정의 되어 있다. 따라서 값을 변경해서 이미 진행된 값인지 표시하는 것은 불가능 하다.
bit를 사용해볼까도 고민해보았는데 문제에는 아래의 제약조건이 있어 포기하였다.
1 <= m, n <= 200
그러면 어떻게든 row, col 하나의 변수를 가지고 처리를 해야한다는 것이다.
힌트 3번을 보면 다음과 같은 내용이 있다.
We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.
이 힌트를 따라 다음과 같은 코드를 작성해보았다.
class Solution {
public void setZeroes(int[][] matrix) {
boolean shouldUpdateFirstRow = false;
boolean shouldUpdateFirstColumn = false;
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
shouldUpdateFirstColumn = true;
break;
}
}
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
shouldUpdateFirstRow = true;
break;
}
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// update row
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
Arrays.fill(matrix[i], 0);
}
}
// update column
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][j] = 0;
}
}
}
// update first row if contains zero
if (shouldUpdateFirstRow) {
Arrays.fill(matrix[0], 0);
}
// update first column if contains zero
if (shouldUpdateFirstColumn) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
}
}
풀이 방법에 대해 설명을 하면 다음과 같다.
- 먼저는 첫번째 행과 열에 0이 있는지 미리 확인해둔다. (
shouldUpdateFirstRow,shouldUpdateFirstColumn) - 이후에는 첫번째 행과 열을 제외하고 0이 발견될 경우 첫번째 행과 열에 0으로 표시해둔다.
- 표시가 끝났으면 첫번째 행과 열을 확인하여 0일 경우 해당 줄, 열을 0으로 업데이트 한다. (단 첫번째 행과 열은 업데이트 하지 않는다.,
i > 0,j > 0) - 업데이트가 끝났다면
shouldUpdateFirstRow,shouldUpdateFirstColumn값을 확인하여 첫번째 행과 열도 0으로 업데이트 해야하는지 확인한다. 필요할 경우 0으로 업데이트 한다.
TC, SC
문제에서 m과 n이 다음과 같이 정의되어 있다.
m == matrix.length
n == matrix[0].length
시간복잡도는 O(n * m) 공간복잡도는 O(1) 이다. 공간 복잡도가 한 번 더 개선되었다.