73. Set Matrix Zeroes

Solution

1. 0의 위치들을 저장한다.
2. 저장된 위치들을 통해 상하좌우를 0으로 만든다.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m = len(matrix)
        n = len(matrix[0])
        pos = []
        for i in range(m):  # 1. 0의 위치 검사 O(m*n)
            for j in range(n):
                if matrix[i][j] == 0:
                    pos.append([i, j])

        for x, y in pos:  # 2. 상하좌우 0으로 만들기 O(0의개수*(m+n))
            for i in range(m):
                matrix[i][y] = 0
            for i in range(n):
                matrix[x][i] = 0

시간 복잡도

1. O(m*n)
2. O(0의개수*(m+n))

이므로 총 시간 복잡도는 O(mn) 이다.

지금 내 코드는 bad idea구나... 더 빠른 방법은 어떻게 해야할까