[NeetCode-LeetCode] Set Matrix Zeroes JAVA

반응형

728x90

[NeetCode-LeetCode] Set Matrix Zeroes - Medium

---

접근

• 수학(?)

---

풀이

행렬에 0이 있는 위치의 행과 열 모든 숫자를 0으로 만드는 문제이다. 0이 있는 위치가 [3,4]이라면 3행에 있는 모든 숫자와 4열에 있는 모든 숫자를 0으로 만드는 것이다. 이 문제에 주어진 추가 질문으로는 O(mn)의 공간 복잡도로 푸는 건 대체적으로 좋지 않은 방법이고 개선하여 O(m+n)의 공간 복잡도로 풀 순 있지만 최선의 방법은 아니다 그렇다면 상수 공간 복잡도로 해결을 해보라는 말인데 상수 공간 복잡도로 해결하려면 추가적인 배열을 사용하지 않아야 한다는 소리다.

     public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true; 
                    col[j] = true; 
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

우선 위는 O(m + n)의 공간 복잡도로 푼 코드이다. 0의 위치를 체크하기 위해 행과 열의 길이를 가진 배열을 사용했다. 0의 위치들을 체크해 두고 해당 좌표가 0과 같은 행이나 열이라면 0으로 바꾸는 과정을 통해 완성하게 된다. 배열을 하나씩 쓴다면 그나마 쉽게 해결이 되지만 상수 공간으로는 너무 복잡한 과정 말고는 감이 안 잡혔다. 

---

상수 공간

상수 공간으로 풀어진 코드를 가져왔다. 가독성을 위해 원본 코드를 살짝 수정했다. 

    public void setZeroes(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        int col = 0, row = 0;

        for (int j = 0; j < n; j++) {
            if (mat[0][j] == 0) {
                col = 1;  
                break;    
            }
        }

        for (int i = 0; i < m; i++) {
            if (mat[i][0] == 0) {
                row = 1;  
                break;   
            }
        }

첫 번째 행과 열의 0을 먼저 체크하고 시작한다. 이 코드의 처리 방식은 첫 번째 행과 열에 마킹을 하여 후처리로 마킹이 된 행과 열 전체를 0으로 바꾸는 방식으로 해결되었다. 

	for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = 0;
                    mat[0][j] = 0;
                }
            }

첫 번째 행열 체크가 끝나면 두 번째 행과 열부터 순회하며 0이 있다면 해당 위치의 첫 번째 행과 열을 0으로 마킹한다. 

	for (int j = 1; j < n; j++) {
            if (mat[0][j] == 0) {
                for (int i = 0; i < m; i++) {
                    mat[i][j] = 0;
                }
            }
        }

        for (int i = 1; i < m; i++) {
            if (mat[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
        }

마킹이 끝나면 마킹했던 첫 번째 행과 열을 기준으로 0으로 변경한다. 

	if (col == 1) {
            for (int j = 0; j < n; j++)
                mat[0][j] = 0;
        }
        
        if (row == 1) {
            for (int i = 0; i < m; i++)
                mat[i][0] = 0;
        }

그리고 변경되지 않았던 첫 번째 행과 열을 마저 변경해 주면 행렬 전체가 변경되게 된다. 

---

전체 코드

O(m + n)

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

        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true; 
                    col[j] = true; 
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

 

상수 공간

class Solution {
    public void setZeroes(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        int col = 0, row = 0;

        for (int j = 0; j < n; j++) {
            if (mat[0][j] == 0) {
                col = 1;  
                break;    
            }
        }

        for (int i = 0; i < m; i++) {
            if (mat[i][0] == 0) {
                row = 1;  
                break;   
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = 0;
                    mat[0][j] = 0;
                }
            }
        }

        for (int j = 1; j < n; j++) {
            if (mat[0][j] == 0) {
                for (int i = 0; i < m; i++) {
                    mat[i][j] = 0;
                }
            }
        }

        for (int i = 1; i < m; i++) {
            if (mat[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
        }

        if (col == 1) {
            for (int j = 0; j < n; j++)
                mat[0][j] = 0;
        }
        
        if (row == 1) {
            for (int i = 0; i < m; i++)
                mat[i][0] = 0;
        }
    }
}