LeetCode 73(Set Matrix Zeros, Python)

1. 문제 링크

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

Set Matrix Zeroes - LeetCode

2. 문제 설명

• mxn 정수 매트릭스 matrix가 주어져있을 때, 만약 element의 값이 0이면, 그 값을 기준으로 row와 column을 0으로 바꾸는 것
• constraint가 없었다면 easy문제였을 수 있는데 "In place"로 해결해야 하는 조건이 붙어있음 
• 예시1)
  • matrix = [[1,1,1],[1,0,1],[1,1,1]]이면 1행, 1열을 전부 0으로 변경하여 output = [[1,0,1],[0,0,0],[1,0,1]]
• 예시2)
  • matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 이면, 0행 0열, 및 0행 4열을 전부 0으로 변경
  • output = [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

3. 처음 풀이

• in-place로 matrix 자체에 값을 수정해야 하기 때문에 0을 마주치고, 그 0이 속한 행과 열을 0으로 바꿔버리면,
  • 바뀐 0들에 의해서 또 다른 행과 열이 0으로 바뀔 수 있기 때문에 무턱대고 바꾸면 안된다 생각 
• 그래서 고민하다가, zero가 있는 행과 열을 tuple 형태로 append를 시킨 뒤, 
• 그 zero_list에 있는 행과 열에 대해서만 0으로 변경하는 것으로 코드 작성
• 여기서의 문제는 runtime은 97.14%로 잘 나왔으나, memory가 5% beats로 낮은 편이었음.
• 상수 공간만 사용해서 해야 공간복잡도가 낮아지는데, 어쨌든 matrix에서 0 값이 있으면 이 행 열을 빈 리스트에 다 쌓아두기 때문에, 메모리 효율이 낮은 것. 

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

        for i_index, i in enumerate(matrix):
            if 0 in i:
                for j_index, j in enumerate(i):
                    if j == 0:
                        zero_list.append((i_index,j_index))
        
        for i in zero_list: 
            for j_index, j in enumerate(matrix[i[0]]):
                matrix[i[0]][j_index] = 0
            for k_index, k in enumerate(matrix):
                matrix[k_index][i[1]] = 0

 

4. 다른 풀이 

• 공간복잡도를 상수로 한 풀이
  
  • 첫 열과 첫 행에 0이 있는지를 check하여 Boolean값으로 저장 (이것 외에는 별도로 저장하는 Variable 없음)
  • 두번째 열, 두번째 행 부터 for문을 돌면서, 값이 0이면
    • 전체를 다 0으로 바꾸지 않고, 우선은 첫번째 행 / 첫번째 열에만 0으로 값을 변경
      • 그리고 첫번째 행, 첫번째 열에 0이 있는 경우, 그 행과 열을 0으로 변경
    • 마지막으로, 첫 번째 행과 첫 번째 열에 0값 처리 

python
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        first_row_has_zero = False
        first_col_has_zero = False
        rows = len(matrix)
        cols = len(matrix[0])

        # 첫 번째 행에 0이 있는지 확인
        for i in range(cols):
            if matrix[0][i] == 0:
                first_row_has_zero = True
                break

        # 첫 번째 열에 0이 있는지 확인
        for i in range(rows):
            if matrix[i][0] == 0:
                first_col_has_zero = True
                break

        # 0이 있는 위치를 첫 번째 행과 첫 번째 열의 해당 요소에 표시
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # 첫 번째 행과 첫 번째 열을 기준으로 0으로 설정
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        # 첫 번째 행과 첫 번째 열 처리
        if first_row_has_zero:
            for i in range(cols):
                matrix[0][i] = 0

        if first_col_has_zero:
            for i in range(rows):
                matrix[i][0] = 0

 

5. 배운 점

• in-place, 공간복잡도