[LeetCode] 73. Set Matrix Zeroes

73. 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.

m X n 크기의 정수 행렬 matrix가 주어질 때, 특정 원소가 0이라면 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하십시오.

 

Example

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

 

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]]

---

1. 문제 요구사항 분석

0 원소 상하좌우를 0으로 변경

 

2. 접근 전략

1. 0이 있는 위치를 기록하기 

2. 0으로 덮어쓰기

 

첫 번째 방법

import java.util.*;

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 1. 원래 0인 위치의 좌표(i, j)를 저장할 리스트 생성
        ArrayList<int[]> list = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    // int[] zero = {i, j}; 로 축약 가능합니다.
                    int[] zero = {i, j};
                    list.add(zero);
                }
            }
        }

        // 2. 리스트에 저장된 좌표를 하나씩 꺼내서 해당 행과 열을 0으로 변경
        for (int[] pos : list) {
            int row = pos[0];
            int col = pos[1];

            // 해당 행(row) 전체를 0으로 변경
            for (int j = 0; j < n; j++) {
                matrix[row][j] = 0;
            }

            // 해당 열(col) 전체를 0으로 변경
            for (int i = 0; i < m; i++) {
                matrix[i][col] = 0;
            }
        }
    }
}

 

 

두 번째 방법

class Solution {
    public void setZeroes(int[][] matrix) {
        // 예외 처리: 행렬이 비어있으면 종료
        if (matrix == null || matrix.length == 0) return;

        int m = matrix.length;    // 행(row)의 개수
        int n = matrix[0].length; // 열(column)의 개수

        // 1. 첫 번째 행과 열에 원래 0이 있었는지 따로 기록
        boolean isFirstRowZero = false;
        boolean isFirstColZero = false;

        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                isFirstRowZero = true;
                break;
            }
        }

        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                isFirstColZero = true;
                break;
            }
        }

        // 2. 내부 칸(1,1부터 시작)을 돌면서 0을 발견하면 
        // 해당 행의 첫 칸과 열의 첫 칸에 '0'이라고 표시(기록)
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // i행은 0이 되어야 함을 표시
                    matrix[0][j] = 0; // j열은 0이 되어야 함을 표시
                }
            }
        }

        // 3. 첫 번째 행과 열에 기록된 '0' 표시를 보고 내부 칸들을 0으로 채움
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 현재 칸의 행 시작점이나 열 시작점에 0이 표시되어 있다면
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 4. 마지막으로, 처음에 따로 보관했던 첫 행/열의 원래 상태를 적용
        // 첫 번째 행 전체를 0으로 변경해야 하는 경우
        if (isFirstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // 첫 번째 열 전체를 0으로 변경해야 하는 경우
        if (isFirstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

 

구분	ArrayList 사용 방식	현재 최적화 방식
시간 복잡도	O(M X N)	O(M X N)
공간 복잡도	O(M X N)	O(1)