[LeetCode] 73. Set Matrix Zeroes - Java

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

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.

 

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
• -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?

---

풀이

풀이 과정

2차원 배열 matrix가 주어질 때 셀의 값이 0인 행과 열은 모두 0으로 치환해야하는 문제이다.

방법은 크게 세 가지로 나눌 수 있다.

• 공간복잡도 O(mn)

주어진 matrix와 똑같은 2차원 배열을 복사하여 복사한 배열을 순회하며 값이 0인 경우 matrix 배열에서 해당 행과 열을 0으로 변경

• 공간복잡도 O(m + n)

matrix의 행과 열의 길이만큼의 배열(m, n)을 생성하여 각각 해당 행과 열이 0으로 세팅되어야 하는지 판단하는데 사용, matrix의 값을 순회하면서 값이 0인경우 m과 n배열의 각 인덱스를 0으로 세팅하고 마지막에 m과 n배열을 순회하며 값이 0인 행과 열의 값을 변경

• 공간복잡도 O(1) 

O(m + n)과 풀이 방법은 같으나 m과 n배열을 따로 생성하지 않고 matrix배열 자체를 이용한다.
첫 번째 행을 n배열로 사용하고 첫 번째 열을 m배열로 사용한다. 다만 [0][0]번째 값은 행과 열에서 겹치므로 하나의 변수를 사용하여 행과 열중 하나를 판단하는데 사용한다.

문제에서 O(mn), O(m + n)의 공간 복잡도보다 효율적인 풀이를 요구하고 있으므로 마지막 방법을 이용하여 풀이한다.

우선 첫 번째 행이나 첫 번째 열을 판단하기 위한 변수를 하나 선언해야한다. 이번 문제에서는 이 변수를 첫 번째 행을 판단하기 위해 사용한다.

// 배열의 첫 번째 행과 열은 해당 행과 열을
// 0으로 치환해야하는지 판단하는데 사용

// 첫 번째 행을 0으로 채워야하는지 판별하기 위한 변수
// 첫 번째 행과 첫 번째 열은 겹치기 때문에 행 판단을 위한 변수를 따로 사용
boolean firstRow = false;

 

matrix 배열의 각 행과 열을 순회하면서 각 값이 속하는 행과 열이 0이 되어야 하는지 탐색한다.
만약 탐색중인 값이 0인 경우 해당 열의 첫 번째 행 값을 0으로 설정한다.
마찬가지로 해당 행의 첫 번째 열 값도 0으로 설정해야 하는데 첫 번째 행의 경우 firstRow라는 변수를 따로 사용하므로 조건을 분기하여 첫 번째 행인 경우 firstRow를 업데이트하고 첫 번째 행이 아닌경우에는 첫 번째 열 값을 업데이트한다.

// 배열의 각 행,열을 탐색하여
// 각 행과 열의 0 치환 여부를 판단
for(int i = 0; i < matrix.length; i++){
    for(int j = 0; j < matrix[0].length; j++){
        // 현재 탐색중인 값이 0이라면
        if(matrix[i][j] == 0) {
            // 현재 열은 0으로 치환해야하는 것으로 판단
            matrix[0][j] = 0;

            // 첫 번째 행이 아닌 경우
            // 현재 행은 0으로 치환해야하는 것으로 판단
            if(i > 0) matrix[i][0] = 0;
            // 첫 번째 행인 경우
            // 첫 번째 행은 0으로 치환해야하는 것으로 판단
            else firstRow = true;
        }
    }
}

 

탐색이 종료되면 첫 번째 행과 열의 값에 따라 해당 행과 열의 값을 0으로 바꿔주어야한다.
첫 번째 행과 열은 다른 값을 바꾸기위해 사용해야 하므로 나머지 행과 열의 값부터 바꾼 후 마지막에 첫 번째 행과 열의 값을 업데이트 한다.

// 첫 번째 행,열을 제외한 나머지 셀 값 치환
for(int i = 1; i < matrix.length; i++) {
    for(int j = 1; j < matrix[0].length; j++) {
        // 탐색중인 행이 0이거나 열이 0인 경우
        // 현재 값을 0으로 변경
        if(matrix[i][0] == 0 || matrix[0][j] == 0) {
            matrix[i][j] = 0;
        }
    }
}

// 첫 번째 열이 0인 경우
if(matrix[0][0] == 0) {
    // 첫 번째 열의 모든 값을 0으로 변경
    for(int i = 0; i < matrix.length; i++) {
        matrix[i][0] = 0;
    }
}

// 첫 번째 행이 0인 경우
if(firstRow) {
 // 첫 번째 행의 모든 값을 0으로 변경
    for(int i = 0; i < matrix[0].length; i++) {
        matrix[0][i] = 0;
    }
}

---

최종 코드

class Solution {
    public void setZeroes(int[][] matrix) {
        // 배열의 첫 번째 행과 열은 해당 행과 열을
        // 0으로 치환해야하는지 판단하는데 사용
        
        // 첫 번째 행을 0으로 채워야하는지 판별하기 위한 변수
        // 첫 번째 행과 첫 번째 열은 겹치기 때문에 행 판단을 위한 변수를 따로 사용
        boolean firstRow = false;
        
        // 배열의 각 행,열을 탐색하여
        // 각 행과 열의 0 치환 여부를 판단
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                // 현재 탐색중인 값이 0이라면
                if(matrix[i][j] == 0) {
                    // 현재 열은 0으로 치환해야하는 것으로 판단
                    matrix[0][j] = 0;
                    
                    // 첫 번째 행이 아닌 경우
                    // 현재 행은 0으로 치환해야하는 것으로 판단
                    if(i > 0) matrix[i][0] = 0;
                    // 첫 번째 행인 경우
                    // 첫 번째 행은 0으로 치환해야하는 것으로 판단
                    else firstRow = true;
                }
            }
        }
        
        // 첫 번째 행,열을 제외한 나머지 셀 값 치환
        for(int i = 1; i < matrix.length; i++) {
            for(int j = 1; j < matrix[0].length; j++) {
                // 탐색중인 행이 0이거나 열이 0인 경우
                // 현재 값을 0으로 변경
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 첫 번째 열이 0인 경우
        if(matrix[0][0] == 0) {
            // 첫 번째 열의 모든 값을 0으로 변경
            for(int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
        
        // 첫 번째 행이 0인 경우
        if(firstRow) {
         // 첫 번째 행의 모든 값을 0으로 변경
            for(int i = 0; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
    }
}

---