leetcode medium : Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/description/

Set Matrix Zeroes

풀기 전

• 첫 row와 column에 마킹을 해두면 될거같다.

코드 설명

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        firstRowZero = False
        firstColZero = False

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    if i == 0:
                        firstRowZero = True
                    if j == 0:
                        firstColZero = True

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

        if firstRowZero:
            matrix[0] = [0] * len(matrix[0])
        
        if firstColZero:
            for i in range(len(matrix)):
                matrix[i][0] = 0

첫 row와 첫 column을 상태 저장용으로 쓴다. 값이 0인게 발견되면 해당 row와 column의 첫요소를 0으로 마킹해둔다. 그리고 나중에 첫 row와 column을 스캔해가면서 값이 0이면 해당 row나 column을 0으로 치환한다.

주의할점은 matrix[0][0]인데, 첫 row나 column에 0이 있으면 matrix[0][0]도 0으로 마킹된다. matrix[0][0]이 0으로 마킹되는건 3가지 의미를 가질 수 있다.

1. 첫 row가 0으로 초기화 되어야 한다.
2. 첫 column이 0으로 초기화 되어야 한다.
3. 둘다 0으로 초기화 되어야 한다.

이를 관리하기 위해 두 가지 상태값을 따로 만들어준다. (firstRowZero, firstColZero)

복잡도 분석

공간복잡도는 당연히 O(1)이고

시간복잡도는 O(MN)이다.