리트코드 - 73. Set Matrix Zeroes

리트코드 - 73. Set Matrix Zeroes

출처 - https://leetcode.com/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

m x n 정수 행렬이 주어지면 요소가 0이면 전체 행과 열을 0으로 설정합니다.
배열 안에서 해야 합니다.

 

풀이코드

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

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

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

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

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

        if (firstRowZero) {
            for (int i = 0; i < n; i++) {
                matrix[i][0] = 0;
            }
        }

        if (firstColZero) {
            for (int j = 0; j < m; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

코드설명

문제에서 In place라고 명시를 했기 때문에 별도의 자료구조를 사용하지 않고 풀어야 하는 문제다.

위의 풀이코드는 In-Place Algorithm이라고도 불리는 기법인데, 별도의 추가 공간을 사용하지 않고 상수시간 만큼의 메모리만 사용하여 문제를 푸는 방법이다.

 

추가 공간을 사용한 풀이는 아래 내 코드 에서 볼 수 있다.

 

간단하게 생각하면 생기는 문제점

문제에서 배열에 0이 있으면 행과 열에 0을 채우면 되는 간단한 문제이다.

간단하게 생각해서 0을 발견했을 때 배열값을 곧바로 변경한다면, 반복문을 돌 때 다음값에 영향을 주게 된다.

예를 들어 첫번째 행을 도는 반복문에서 0을 발견했을 때 가로와 세로를 모두 0으로 채워보자.

가로와 세로는 이렇게 채워질 것이다.

다시 두번째 반복문을 돌 때는 첫번째 반복문에서 채워진 0을 발견해서 다시 가로와 세로를 0으로 채워버릴 것이다.

원래 두번째 행에는 0이 없었다. 첫번째 반복문에서 수행한 결과로 두번째에 0이 생겼고 이 0은 원래 있던 값이 아니므로 채워지면 안된다.

즉, 원하는 의도가 아니다.

 

해결방법

첫번째 수행이 두번째에 영향을 미친다면 1) 0을 발견하는 것과 2)0으로 채우는 것을 각각 분리해서 생각하면 된다.

 

1. 어떻게 0을 체크할 것인가?

2. 어떻게 채울 것인가?

 

여기서의 풀이방법은 첫 행과 첫 열을 먼저 검사해서 0이 있는지 각각 확인해서 boolean으로 먼저 저장해 놓는다.

그리고 첫 행과 첫 열을 체크포인트로 만들어버리는 방법이다.(1번 해결)

무슨 소리냐면, 어떤 행과 열에서 0을 발견한다면 그 행과 열의 첫번째에 0을 기록해놓는 것이다.

이렇게 해서 반복문을 돌며 0을 기록해놓는게 첫번째이다.

반복문을 다 돈 다음에는 다시 첫 행과 첫 열은 제외한 반복문을 돈다.

이 때 해당 위치의 첫 행과 첫 열을 확인해서 값이 하나라도 0이면 0을 대입한다.(2번 해결)

 

예를 들어 위의 경우 빨간빗금 친 부분에선 어떤 값이 될까?

첫번째 열에서 0이 발견되므로 0으로 채워질 것이다.

체크포인트에 0이 없다면 0으로 채우면 안되는 값이다.

 

이런식으로 반복문을 돌고, 마지막으로 아까 완성하지 못한 첫 행과 첫 열을 완성시켜야 한다.

맨 처음에 저장했던 boolean값 두 개를 확인해서 true면 해당하는 행 또는 열을 0으로 채워주면 문제가 해결된다.

 

순서가 달라지면 틀린 풀이가 되므로 아래 순서를 꼭 지켜야 한다.

 

1. 첫 행과 첫 열에서 0 있는지 확인

2. 반복문을 돌며 0이면 각 좌표 첫번째 값에 0 표기

3. 반복문을 다시 돌며 0이 표기된 행과 열은 0으로 변경

4. 첫 행과 첫 열 처리하여 마무리

 

시간복잡도 - O(N*M)

공간복잡도 - O(N) (n 또는 m. 큰 크기가 곧 최대공간복잡도)

 

문제를 풀며 생각한 흐름과 배운 점

처음 풀은 코드

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        List<Integer> xIdxs = new ArrayList<>();
        List<Integer> yIdxs = new ArrayList<>();

        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    xIdxs.add(i);
                    yIdxs.add(j);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int y : yIdxs) {
                matrix[i][y] = 0;
            }
        }

        for (int j = 0; j < m; j++) {
            for (int x : xIdxs) {
                matrix[x][j] = 0;
            }
        }
    }
}

처음에 풀었던 논리의 흐름은 풀이코드와 비슷했다.

단지 처리하는 방식에서 차이가 있었다.

 

1. 어떻게 0을 체크할 것인가? -> x인덱스, y인덱스를 저장하는 List 생성

2. 어떻게 채울 것인가? -> 각 인덱스의 반대쪽 좌표의 반복문을 돌려서 0으로 채움.

 

다만 이 풀이는 새로운 공간을 사용한다는 점에서는 효율적인 면에서 아쉬운 코드가 되었다.

 

정리

In-Place Algorithm 사용법