[Leetcode 아주 상세한 문제풀이] 73. Set Matrix Zeroes - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 73번 문제 Set Matrix Zeroes 다.

우선 문제를 살펴보자.

 

리트코드 73번 문제 Set Matrix Zeroes 링크

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

Set Matrix Zeroes - LeetCode

 

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

 

Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

Follow up:
A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

 

 

문제 설명

문제에 대해 간략히 살펴보자.

우선 m by n 사이즈의 2D array가 주어지는데, 이 배열 안에 0이 존재한다면 그 0이 있는 행과 열을 모두 0으로 바꾸라는 문제다.

위의 예시 1번에서 보는 것처럼 0이 두번째 행, 두번째 열에 위치기 있기 때문에 두번째 행과 열 모두를 0으로 바꿔 출력하라는 문제다.

문제가 단순하기 때문에 곧바로 문제를 풀어보자.

 

 

문제 접근법1

이 문제를 푸는 가장 직관적인 방법은 배열 전체를 탐색해 0의 위치를 기억한 뒤,

그 위치에 0을 넣으면 쉽게 해결할 수 있다.

하지만 문제의 말미에 명시되어 있듯이 O (mn) space 이용하여 문제를 푸는 방식은 나쁜 아이디어 일수도 있다고 한다.

 

문제 풀이1

그래도 우선 문제를 한 번 풀어보자.

우선 배열을 입력받을 함수를 정의해 준다 (line 1)

그리고 matrix의 행/열 사이즈를 확인해준다 (line 2)

그 후 배열 전체를 double for loop를 이용하여 탐색하는데 (line 6-7)

이때 배열 값이 0 이라면 그 위치 (행/열)를 기억해둔다 (line 8-9)

그리고 기억해둔 행과 열 전체를 double for loop를 이용하여,

값을 0으로 치환해준다 (line 13-16)

 

 

문제 풀이 코드1

def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    zero_positions = []
 
    # Find the zero positions
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0:
                zero_positions.append((i, j))
 
    # Set rows and columns to zero based on zero positions
    for i, j in zero_positions:
        for k in range(cols):
            matrix[i][k] = 0
        for k in range(rows):
            matrix[k][j] = 0
 
# Test cases
matrix1 = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
setZeroes(matrix1)
print(matrix1)
 
matrix2 = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
setZeroes(matrix2)
print(matrix2)

 

 

문제 접근법2

이 방식이 가장 직관적인 방식이긴 하지만 우리는 좀 더 효율적인 문제풀이 방식을 찾아볼 필요가 있다.

문제의 말미에 써있듯 constant space를 이용하여 문제를 한 번 풀어보자.

결국 문제에서 요구하는 바는 주어진 행렬에서 0이 위치한 곳의 행과 열 모든 값을 0으로 치환하라는 것이다.

즉, 주어진 행렬의 모든 값을 탐색해 위치를 저장하고, 그 위치에 0으로 치환해주기 보다는,

주어진 행렬의 첫번째 행과 열만을 이용해

만약 전체 행렬을 탐색하며 0이 발견되다면 그 위치에 해당하는 첫번째 행과 열 값을 0으로 치환한다.

결과적으로 이 과정을 끝내고 나면 0으로 치환해야 행 행과 열이 첫번째 행과 열에서 0의 값을 갖게 된다.

 

예를 들어 아래와 같은 3 by 3 행렬이 주어진다고 했을 때

두번째 행과 세번째 행은 0을 포함하고 있으므로 0번째 행에 x 표시를 해주고

첫번째 열과 세번째 열은 0을 포함하고 있으므로 0번째 열에 x 표시를 해준다.

 

결과적으로 우리는 x표시가 된 행과 열의 모든 값을 0으로 치환해 아래와 같은 결과를 얻게 된다.

 

결국 이 방식은 첫번째 행과 열만 업데이트 하기 때문에 constant space (m + n)을 갖게 된다.

 

 

문제 풀이2

코드를 한 번 살펴보자.

우선 배열을 입력받을 함수를 정의해 준다 (line 1)

그리고 그 행렬의 행/열 사이즈를 확인한다 (line 2)

우리는 첫번째 행과 열을 업데이트 해줄것이기 때문에,

any 함수를 이용하여 첫번째 행과 열에 0이 존재하는지 판단하는 변수를 만들어준다 (line 3-4)

any 함수는 iterable 한 item이 하나라도 있는지 판단하는 함수인데,

예를 들어 주어진 배열이 [0, 0, 0] 혹은 [False, False, False] 라면 False를,

[1, 0, 0] 혹은 [True, False, Flase] 라면 True를 출력해 준다.

즉 여기에서는 첫번째 행과 열에 True가 하나라도 있다면 (0이 하나라도 존재한다면) True를 출력해준다.

첫번째 행과 열은 업데이트 하는데 사용되기 때문에

우리는 두번째 행과 열부터 doubple for loop를 사용해 탐색해주며 (line 7-8)

만약 해당하는 값이 0이라면 그때의 첫번째 행과 열의 값을 0으로 업데이트 해준다 (line 9-10)

그 후 double for loop를 사용하여 첫번째 행과 열을 탐색하는데 (line 13-14)

이때 첫번째 행과 열 둘 중 하나라도 0의 값을 가지고 있다면,

해당하는 값을 0으로 치환해준다 (line 15-16)

마지막으로 할 것이 하나 더 있다.

우리는 첫번째 행과 열을 0이 있는지 없는지 적어두는 곳으로 사용했기 때문에,

마지막에 첫번째 행과 열에 0이 있는지 판단하여

0이 존재한다면 그 행과 열에 해당하는 값을 모두 0으로 치환해준다 (line 19-25)

 

 

문제 풀이 코드2

def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_has_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_has_zero = any(matrix[i][0] == 0 for i in range(rows))
 
    # Use the first row and first column to mark zero positions
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
 
    # Set elements to zero based on the first row and first column marks
    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
 
 
    # Set first row and first column to zero if they were marked
    if first_row_has_zero:
        for j in range(cols):
            matrix[0][j] = 0
 
    if first_col_has_zero:
        for i in range(rows):
            matrix[i][0] = 0
 
# Test cases
matrix1 = [[0, 0, 0], [0, 1, 1], [0, 1, 1]]
setZeroes(matrix1)
print(matrix1)
 
matrix2 = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
setZeroes(matrix2)
print(matrix2)
 

 

 

관련 문제

리트코드 48번 Rotate image 문제 풀이 (링크)

리트코드 54번 Spiral matrix 문제 풀이 (링크)

리트코드 79번 Word search 문제 풀이 (링크)

 

 

73. Set Matrix Zeroes