Leet code (Medium): 73. Set Matrix Zeroes - JAVA

 

위 문제를 Set을 사용하여 공간 복잡도 O(m+n)으로 풀고,

별도 객체 생성 없이 O(1)로도 풀어보았다.

 

O(1)로 풀기 위해선 이 문제의 특징을 잘 알아야한다.

0인 곳의 모든 행과 열을 0으로 바꾸는 문제이기 때문에,

첫번째 행, 첫번째 열만 돌면서 해당하는 행과 열에 0이 있는지 체크하고 0으로 바꿔두면 된다.

 

시간 복잡도는 두가지 방법 모두 O(m x n) 이다.

1. 공간 복잡도 O(m+n)

class Solution {
    public void setZeroes(int[][] matrix) {
        
        Set<Integer> zRow = new HashSet<>();
        Set<Integer> zCol = new HashSet<>();

        for(int row = 0; row < matrix.length; row++){
            for(int col = 0; col < matrix[0].length; col++){
                if(matrix[row][col] == 0){
                    zRow.add(row);
                    zCol.add(col);
                }
            }
        }

        for(int row = 0; row < matrix.length; row++){
            for(int col = 0; col < matrix[0].length; col++){
                if(matrix[row][col] != 0){
                    if(zRow.contains(row) || zCol.contains(col)){
                        matrix[row][col] = 0;
                    }
                }
            }
        }
    }
}

 

 

2. 공간복잡도 O(1)

class Solution {
    public void setZeroes(int[][] matrix) {
    	// 첫번째 행과 열은 해당 행과 열에 0이 있는지 없는지를 체크하는 공간으로 사용되기 때문에,
        // 첫번째 행과 열에 0이 있는지 없는지를 따로 저장해서 => (firstRowZero,firstColZero)
        // 첫번째 행과 열을 제외한 나머지를 전부 첫번째 행과 열을 보고 0으로 업데이트를 다 한 후,
        // 첫번째 행과 열도 firstRowZero,firstColZero값을 보고 0으로 바꿔줘야한다.
        boolean firstRowZero = false, firstColZero = false;
        int rows = matrix.length, cols = matrix[0].length;

        // 1. 첫 번째 행과 열에 0이 있는지 확인
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) firstColZero = true;
        }
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }

        // 2. 나머지 행과 열에 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;
                }
            }
        }

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

        // 4. 처음에 체크했던 첫 번째 행과 열을 0으로 설정
        if (firstColZero) {
            for (int i = 0; i < rows; i++) {
                matrix[i][0] = 0;
            }
        }
        if (firstRowZero) {
            for (int j = 0; j < cols; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

 

여기서 첫 번째 행과 첫 번째 열에 0이 있는 경우를 별도로 처리해야 하는 이유는,

첫 번째 행과 열이 표시용 공간으로 이미 사용되기 때문이다.

 

• 첫 번째 행과 열은 다른 행과 열에 0이 있는지 표시하는 용도로 사용되고 있다.
  즉, 행렬의 나머지 부분에서 0을 발견하면, 그 정보를 첫 번째 행과 첫 번째 열에 기록하고 나중에 사용한다.
• 이때, 첫 번째 행과 열 자체가 0을 포함하고 있는지 여부를 동시에 저장할 방법이 필요하다.
  그렇지 않으면, 표시 과정에서 첫 번째 행과 열에 대한 원래 정보가 덮어써져 버릴 수 있다.