Set Matrix Zeroes

Q: Set Matrix Zeroes의 시간 복잡도는 얼마인가요?

m × n 행렬의 경우 O(m·n)입니다. 모든 셀을 일정한 횟수만큼 읽고 쓰기 때문입니다. 건너뛴 셀이 답을 바꾸는 0일 수 있으므로 이보다 더 효율적인 해법은 없습니다. 표시 배열을 사용하면 추가 공간은 O(m + n)이고, 첫 번째 행과 열을 표시자로 사용하면 O(1)입니다.

보통배열과 문자열 해싱

+10

입력은 정수로 이루어진 m × n 격자이며, 행별로 주어집니다. 따라서 matrix[i][j]는 i행 j열에 있습니다. 격자에서 0인 값이 있는 곳마다 해당 행 전체와 열 전체를 0으로 설정하세요. 처음부터 있던 0만 해당합니다. 0으로 바꾼 셀은 자신의 행이나 열을 0으로 만들지 않습니다. 격자를 제자리에서 변경해도 됩니다. 격자를 반환하세요.

함수

setZeroes(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: 정수 격자, 각 행마다 하나의 내부 목록
반환값integer-2d-array: 0이 포함된 모든 행과 모든 열을 0으로 설정한 행렬

제약 조건

m == matrix.length 그리고 n == matrix[i].length
1 ≤ m, n ≤ 1000 그리고 m × n ≤ 5000
모든 m개의 행에는 n개의 값이 들어 있습니다.
-1000 ≤ matrix[i][j] ≤ 1000

예제

입력: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
출력: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
설명: 유일한 0은 1행 1열에 있습니다. 1행은 모두 0이 되고, 1열도 마찬가지여서 8과 6이 0으로 바뀝니다. 네 모서리는 어느 쪽 줄에도 속하지 않으므로 값을 그대로 유지합니다.

후속 질문

아래의 가장 좋은 방법은 추가 불리언 값 두 개를 유지합니다. matrix[0][0]이 첫 번째 행을 나타내도록 해서 하나만으로 해결할 수 있을까요?

풀이

직접 쓴 0은 주어진 0과 똑같아 보이므로, 탐색하는 동안 행을 지우면 행렬 전체에 0이 퍼집니다. 읽기와 쓰기를 분리하세요. 먼저 어떤 행과 열에 0이 있었는지 기록한 다음, 해당 행과 열을 지우세요. 이 기록은 두 개의 배열에 저장하거나, 추가 공간을 O(1)만 사용하려면 행렬의 첫 번째 행과 열에 저장하세요.

두 배열에서 행과 열 표시하기

핵심 아이디어

셀은 시작 시점에 해당 행이나 열에 0이 있었던 경우에만 0이 됩니다. 따라서 쓰기를 하지 않는 한 번의 순회에서 zeroRow[i]와 zeroCol[j]라는 두 가지 사실 목록을 기록한 다음, 행이나 열이 표시된 모든 셀을 지우세요. 모든 읽기가 첫 번째 쓰기 전에 끝나므로 0이 퍼지지 않습니다.

각 순회는 m·n개의 셀을 한 번씩 방문하므로 시간 복잡도는 O(m·n)이고, 배열에는 m + n개의 불리언 값이 들어갑니다.

알고리즘

m개의 항목으로 구성된 zeroRow와 n개의 항목으로 구성된 zeroCol을 만들고, 모두 false로 설정합니다.
모든 셀을 검사합니다. matrix[i][j]가 0이면 zeroRow[i]와 zeroCol[j]를 true로 설정합니다.
모든 셀을 다시 검사하고 zeroRow[i] 또는 zeroCol[j]가 true이면 해당 셀을 0으로 설정합니다.
행렬을 반환합니다.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_row[i] = True
                zero_col[j] = True
    # Pass 2: write.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

첫 번째 행과 열을 표시자로 사용하세요

핵심 아이디어

첫 번째 열에는 각 행마다 셀이 하나씩 있고 첫 번째 행에는 각 열마다 셀이 하나씩 있는데, 이것이 두 마커 배열의 모양입니다. 따라서 행 i, 열 j의 0은 matrix[i][0]과 matrix[0][j]에 0을 기록합니다. 정보가 손실되지는 않습니다. 이 셀들은 어차피 0으로 바뀌어야 하는 행이나 열에 있기 때문입니다.

0행과 0열은 데이터이면서 마커이기도 하므로, 여기에 마커를 기록하면 원래 그 셀에 0이 있었는지 알 수 없게 됩니다. 따라서 먼저 확인하고 그 결과를 두 개의 불리언에 저장하세요. i ≥ 1 및 j ≥ 1인 셀에만 마커를 기록하고 값을 채운 다음, 마지막으로 0행과 0열을 지우세요. 값을 채울 때 이 행과 열을 읽기 때문입니다.

두 번째 예시에서는 행 1, 열 1의 3이 그대로 남습니다. 해당 마커인 matrix[1][0] = 9와 matrix[0][1] = 4가 0이 아니기 때문입니다. 추가 메모리는 불리언 두 개이므로 시간 복잡도는 O(m·n)으로 유지됩니다(R에서는 입력을 먼저 복사하므로 O(m·n)입니다).

알고리즘

행 0에 0이 있으면 firstRowZero를 설정하고, 열 0에 0이 있으면 firstColZero를 설정합니다.
0이 있는 i ≥ 1 및 j ≥ 1인 모든 셀에 대해 matrix[i][0]과 matrix[0][j]를 0으로 설정합니다.
i ≥ 1 및 j ≥ 1인 모든 셀에 대해 matrix[i][0] 또는 matrix[0][j]가 0이면 해당 셀을 0으로 설정합니다.
firstRowZero가 참이면 행 0을 0으로 설정합니다. firstColZero가 참이면 열 0을 0으로 설정합니다.
행렬을 반환합니다.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    # Mark: a zero inside the matrix flags its row in column 0
    # and its column in row 0.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    # Fill the inside from the markers.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    # The marker row and column go last.
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0
    return matrix

함정과 경계 사례

0을 찾자마자 행과 열을 지우는 것. 첫 번째 예시에서는 1행 2열에 새로 생긴 0이 2열을 지우고, 왼쪽 위의 3만 남습니다.
matrix[0][0]이 0행과 0열을 모두 표시하게 두는 것. [[1, 2, 3], [0, 5, 6], [7, 8, 9]]에서는 0열의 0 때문에 0행이 잘못 지워집니다.
채우기 전에 0행이나 0열을 지우는 것. [[0, 2, 3], [4, 5, 6], [7, 8, 9]]에서는 모든 열이 표시된 것처럼 보여 행렬 전체가 0이 됩니다.
한 줄짜리 경우를 잊는 것. 행이 하나뿐이면 1부터 시작하는 반복문은 아무것도 하지 않고 불리언 변수들이 모든 작업을 합니다. [[1, 0, 3]]은 [[0, 0, 0]]이 되어야 합니다.

자주 묻는 질문3

행렬을 순회하는 동안 0으로 설정할 수 없는 이유는 무엇인가요?

직접 쓴 0은 원래 있던 0과 똑같아 보입니다. 스캔이 그 0에 도달하면 해당 행과 열을 비우고, 새로 생긴 0이 더 퍼져 나갑니다. 셀을 변경하기 전에 원래 있던 0을 모두 기록하세요.

Set Matrix Zeroes의 시간 복잡도는 얼마인가요?

m × n 행렬의 경우 O(m·n)입니다. 모든 셀을 일정한 횟수만큼 읽고 쓰기 때문입니다. 건너뛴 셀이 답을 바꾸는 0일 수 있으므로 이보다 더 효율적인 해법은 없습니다. 표시 배열을 사용하면 추가 공간은 O(m + n)이고, 첫 번째 행과 열을 표시자로 사용하면 O(1)입니다.

0 대신 특수한 값으로 셀을 표시할 수 있나요?

일부 풀이에서는 지울 셀에 플레이스홀더를 기록한 다음, 마지막에 플레이스홀더를 0으로 바꿉니다. 입력에 플레이스홀더가 절대 나타나지 않는 경우에만 이 방법이 통하는데, 정수 행렬에서는 이를 보장하기 어렵습니다. 각 0에 대해 해당 행과 열에 플레이스홀더를 기록하는 방법은 O(m·n·(m + n))의 시간도 듭니다.

def setZeroes(matrix):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자

matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]

예상 출력

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]