LeetCode 73. Set Matrix Zeroes

Set Matrix Zeroes - LeetCode

 

문제 설명

m x n 크기의 정수 행렬 matrix가 주어진다.

행렬의 원소 중 0이 존재할 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 변경해야 한다.

 

추가 도전

- O(mn) 공간을 사용하는 간단한 해결책은 아마 좋지 않을 것임

- O(m + n) 공간을 사용하는 간단한 개선이 있찌만 여전히 최선의 해결책은 아님

- 상수 공간 복잡도를 가지는 해결책으로 해결해 보자!

 

문제 풀이

| 둘의 시간 복잡도는 O(mn)으로 동일

문제 풀이 1번 => 매트릭스에서 0의 위치를 모두 저장한 후에 처리 (O(m + n) 공간 복잡도)

1. 행렬을 순회하면서 값이 0인 위치를 찾는다

2. 0을 발견하면 해당 위치를 vector<pair<int,int>> 배열에다가 기록함

3. 0의 갯수만큼 해당하는 위치의 행과 열의 모든 값을 0으로 변경함

 

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int y=matrix.size();
        int x=matrix[0].size();
        vector<pair<int,int>> points;
        for(int i=0;i<y;i++)
        {
            for(int j=0;j<x;j++)
            {
                if(matrix[i][j]==0)
                {
                    points.push_back({i,j});
                }
            }
        }
        for(int i=0;i<points.size();i++)
        {
            int row = points[i].first;
            int col = points[i].second;

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

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

 

문제 풀이 2 번 => 0으로 변경해야 하는 행과 열을 별도로 저장하는 방법 (O(m + n) 공간 복잡도)

1. 행렬 전체를 순회하면서 값이 0인 위치를 찾는다.
2. 0을 발견하면 해당 위치의 행과 열을 바로 0으로 변경하지 않고, x, y 배열에 표시해둔다.
   • x[j] = true : j번째 열을 0으로 변경해야 한다는 의미
   • y[i] = true : i번째 행을 0으로 변경해야 한다는 의미
3. 행렬 탐색이 끝난 후 y[i]가 true인 행을 찾아 해당 행의 모든 원소를 0으로 변경한다.
4. 마찬가지로 x[j]가 true인 열을 찾아 해당 열의 모든 원소를 0으로 변경한다.

처음 행렬을 탐색할 때 바로 값을 변경하지 않고, 변경해야 할 행과 열의 정보만 먼저 저장하기 때문에 새롭게 만들어진 0이 이후 탐색에 영향을 주는 것을 방지할 수 있다.

 

 

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int xSize=matrix[0].size();
        int ySize=matrix.size();
        bool x[201]={};
        bool y[201]={};
        for(int i=0;i<ySize;i++)
        {
            for(int j=0;j<xSize;j++)
            {
                if(matrix[i][j]==0)
                {
                    x[j]=true;
                    y[i]=true;
                }
            }
        }
        // true인 행을 전부 0으로
        for(int i = 0; i < ySize; i++)
        {
            if(y[i])
            {
                for(int j = 0; j < xSize; j++)
                {
                    matrix[i][j] = 0;
                }
            }
        }

        // true인 열을 전부 0으로
        for(int j = 0; j < xSize; j++)
        {
            if(x[j])
            {
                for(int i = 0; i < ySize; i++)
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

 

 

문제 풀이 3번 => 첫 번째 행과 열을 마커로 활용하는 방법 (O(1) 공간 복잡도)

1. 별도의 x, y 배열을 사용하지 않고 행렬의 첫 번째 행과 첫 번째 열을 마커로 사용한다.
2. 행렬을 순회하면서 값이 0인 위치를 발견하면 해당 위치의 첫 번째 행과 열에 0을 표시한다.
   • matrix[i][0] = 0 : i번째 행을 0으로 변경해야 한다는 의미
   • matrix[0][j] = 0 : j번째 열을 0으로 변경해야 한다는 의미
3. 첫 번째 행과 첫 번째 열에 저장된 마커를 확인하면서 나머지 원소들을 0으로 변경한다.
4. matrix[0][0]은 첫 번째 행과 첫 번째 열이 겹치는 위치이기 때문에 두 상태를 동시에 저장할 수 없다. 따라서 첫 번째 행을 0으로 만들어야 하는지는 별도의 변수에 저장한다.
5. 마지막으로 첫 번째 행과 첫 번째 열을 각각 저장해둔 정보에 따라 0으로 변경한다.

2번 풀이에서 사용했던 x, y 배열의 역할을 행렬의 첫 번째 행과 첫 번째 열이 대신하도록 하여 추가 공간 복잡도를 O(1)로 줄일 수 있다.

 

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int xSize = matrix[0].size();
        int ySize = matrix.size();

        bool firstRowZero = false;

        // 첫 번째 행과 열을 마커로 사용
        for (int i = 0; i < ySize; i++)
        {
            for (int j = 0; j < xSize; j++)
            {
                if (matrix[i][j] == 0)
                {
                    matrix[0][j] = 0;

                    if (i > 0)
                    {
                        matrix[i][0] = 0;
                    }
                    else
                    {
                        firstRowZero = true;
                    }
                }
            }
        }

        // 마커를 확인하여 나머지 영역을 0으로 변경
        for (int i = 1; i < ySize; i++)
        {
            for (int j = 1; j < xSize; j++)
            {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                {
                    matrix[i][j] = 0;
                }
            }
        }

        // 첫 번째 열 처리
        if (matrix[0][0] == 0)
        {
            for (int i = 0; i < ySize; i++)
            {
                matrix[i][0] = 0;
            }
        }

        // 첫 번째 행 처리
        if (firstRowZero)
        {
            for (int j = 0; j < xSize; j++)
            {
                matrix[0][j] = 0;
            }
        }
    }
};

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다.