leetcode medium : Set Matrix Zeroes

Set Matrix Zeroes - LeetCode

Set Matrix Zeroes - LeetCode

 

결코 쉽지 않은 문제다. 나도 힌트보고 풀었다.

혹여나 dfs나 bfs같은 방법을 떠올리는 사람들은 모두 잊어라. graph search 자체가 인풋데이터 크기에 비례하는 공간을 사용한다. 절대 Constant space가 아님!

 

또한 각 matrix의 원소들은 -2^31 ~ 2^31-1의 범위를 갖는다. 이게 무슨말일까? 파이썬은 big int도 자동 지원하고 리스트 원소의 타입이 정해진게 없으니 None이나 - 2^31-1같은 숫자로 마크해놓고 나중에 0으로 바꿔도 되긴하는데 출제자가 그걸 원한게 당연히 아닐것이다.

 

아이디어는 단순하다. matrix[i][j]가 0이면 matrix[i][0]과 matrix[0][j]를 0으로 마크한다.

즉 0이 나타난 위치가 포함되는 행과 열의 첫 번째 원소를 0으로 마크한다는 것이다.

그럼 나중에 첫번째 행과 첫번째 열의 요소들을 쭉 훑어보면서 0인 행과 열에 대해 모든 원소를 다 0으로 바꿔주면 되니까.

근데 이러면 작은 문제가 하나 발생한다. matrix를 한번 스캔해서 마크를 다 했다고 치자. 이때 첫 번째 행과 첫 번째 열에 있는 0들이 마크된 0인지 아니면 첨에 input으로 주어진 0인지 어떻게 구분해야될까? 만약 모든 0이 마크된 0이면 해당 행이나 열을 모두 0으로 바꿔버리면 안되다. 반면 첫 번째 행과 열의 원소 중 하나라도 진짜 첨부터 0으로 주어진 input이면 그 행이나 열의 숫자를 모두 0으로 바꿔버려야된다. 이걸 위해서 first_column_zero 변수와 first_row_zero 변수를 만들어서 첫 행이나 열에 진짜 0이 포함되어있는지를 boolean으로 저장한다. 이렇게 추가로 필요한 variable은 총 2개다.

 

정리하면

1. matrix 스캔을 시작한다.

2. matrix[i][j]가 0이면 matrix[i][0]와 matrix[0][j]를 0으로 마크하되 만약 i가 0이면 first_row_zero 플래그를 True로 활성화시키고 j가 0이면 first_column_zero 플래그를 True로 활성화시킨다.

3. matrix를 거꾸로 스캔한다.

4. 현재 위치가 i,j일때 matrix[i][0]이나 matrix[0][j]가 0이면 matrix[i][j]를 0으로 assign한다.

만약 i가 0이고 fisrt_row_zero 플래그가 활성화 되어있으면 matrix[i][j]에 0 할당

만약 j가 0이고 first_column_zero 플래그가 활성화 되어있으면 matrix[i][j]에 0 할당

 

두번째 스캔에서 matrix를 거꾸로 스캔하는 이유는 첫번째 행과 열에 있는 정보가 사라지는걸 막기 위함이다. 만약 first_row_zero가 True일경우 순방향스캔하면 첫줄 스캔하자마자 첫 행이 다 0이 되어버려서 어떤 열들이 0이 되어야하는지에 대한 정보가 다 사라진다.

 

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        
        first_row_zero = False
        first_col_zero = False
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    if i == 0:
                        first_row_zero = True
                        continue
                    if j == 0:
                        first_col_zero = True
                        continue
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        for i in range(len(matrix) - 1, -1, -1):
            for j in range(len(matrix[0]) - 1, -1, -1):
                if i == 0 and first_row_zero:
                    matrix[0][j] = 0
                    continue
                if j == 0 and first_col_zero:
                    matrix[i][0] = 0
                    continue
                
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0