[LeetCode] - 73. Set Matrix Zeroes

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Set Matrix Zeroes" 문제입니다.

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

 

문제 : 

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.

---

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output: [[1,0,1],[0,0,0],[1,0,1]]

 

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

 

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

---

이 문제는 주어진 m x n 정수 행렬에서 어떤 요소가 0이면, 그 요소가 속한 전체 행과 열을 0으로 설정하는 문제입니다. 이 작업은 추가 공간을 거의 사용하지 않고 제자리에서 수행되어야 합니다. 

제 코드로 바로 보시겠습니다 : 

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;

        // 첫 번째 행에 0이 있는지 확인
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // 첫 번째 열에 0이 있는지 확인
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }

        // 나머지 행과 열에 0이 있는지 확인하고, 첫 번째 행과 열에 해당 정보를 저장
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 나머지 행과 열을 0으로 설정
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 첫 번째 행을 0으로 설정
        if (firstRowHasZero) {
            for (int j = 0; j < cols; j++) {
                matrix[0][j] = 0;
            }
        }

        // 첫 번째 열을 0으로 설정
        if (firstColHasZero) {
            for (int i = 0; i < rows; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

 

이 코드는 주어진 m x n 정수 행렬에서 요소가 0인 경우, 해당 요소가 속한 전체 행과 열을 0으로 설정하는 문제를 해결합니다. 이 작업은 추가 공간을 거의 사용하지 않고 제자리에서 수행됩니다. 코드의 주요 부분은 다음과 같습니다 :

1. 첫 번째 행과 열에 0이 있는지 확인 :
   • firstRowHasZero와 firstColHasZero 변수를 사용하여 첫 번째 행과 열에 0이 있는지 확인합니다.
2. 나머지 행과 열에 0이 있는지 확인하고, 첫 번째 행과 열에 해당 정보를 저장 :
   • 첫 번째 행과 열을 사용하여 나머지 행렬의 0 위치를 표시합니다.
3. 표시된 정보를 기반으로 나머지 행과 열을 0으로 설정 :
   • 첫 번째 행과 열의 표시된 정보를 기반으로 나머지 행렬의 요소를 0으로 설정합니다.
4. 첫 번째 행과 열을 0으로 설정 :
   • 초기 확인 결과에 따라 첫 번째 행과 열을 0으로 설정합니다.

 

시간 복잡도 :

• O(m * n) :
  • 첫 번째 행과 열을 확인하는 데 O(n) 시간이 걸리고,
  • 나머지 행과 열을 확인하고 표시하는 데 O(m * n) 시간이 걸리며,
  • 표시된 정보를 기반으로 행렬을 업데이트하는 데 O(m * n) 시간이 걸립니다.
  • 따라서 총 시간 복잡도는 O(m * n)입니다.

공간 복잡도 :

• O(1) :
  • 추가적인 행렬이나 리스트를 사용하지 않고, 첫 번째 행과 열을 표시로 사용하는 공간만 필요합니다.
  • 추가적인 변수 공간인 firstRowHasZero와 firstColHasZero만 사용되므로, 공간 복잡도는 O(1)입니다.

이 코드는 시간 복잡도와 공간 복잡도 면에서 효율적이며, 문제에서 요구하는 제자리(in-place) 작업을 잘 수행합니다.

---

Runtime 결과