M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 73 - Set Matrix Zeroes

1 분 소요

문제

73 - Set Matrix Zeroes 풀러가기

문제 분석

Given an *m* x *n* matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

  • A straight forward solution using O(m**n) 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?
in-place란? - 새로운 배열을 만들지 않고, 그 자체 배열을 사용하는 것.

이 문제는 0을 가진 행과 열은 모두 0으로 만드는 것이다.

문제 풀이(C++)

  1. 전체 코드(m*n space)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) { 
            int m = matrix.size();
            int n = matrix[0].size();
            
            vector<bool> r(n, false);
            vector<bool> c(n, false);
            
             for(int i =0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(matrix[i][j] == 0){
                        r[j] = true;
                        c[i] = true;
                    }
                }
            }
            
            for(int i =0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(r[j] || c[i]){
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }
    		cs

    • 이 방법은 가장 단순한 방법이다.

      • matrix의 현재 값이 0 인 경우에 해당 위치의 행과 열을 찾아서, 그 행이나 열을 가지는 모든 위치의 값을 0으로 바꾸는 것이다.
    • 7,8번째 줄 : 특정 row, column에 0이 있는 경우를 표시하기 위해 만든 vector.
    • 10~17번째 줄 : 0이 있다면, 그 위치의 row, column에 0이 있다고 표시
    • 19~25번째 줄 : 위에서 표시한 결과에 따라, 행/열 둘중에 하나라도 0이 있다고 하면 해당 위치의 matrix값을 0으로 바꿔준다.
    notice - 문제에서 using O(*m**n*) space is probably a bad idea.라고 되어있다. 따라서 다른 방법을 찾아봐야 한다.

  2. 전체 코드(다른 방법)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) { 
            int m = matrix.size();
            int n = matrix[0].size();
     
            set<int> r;
            set<int> c;
           
             for(int i =0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(matrix[i][j] == 0){
                        r.insert(i);
                        c.insert(j);
                    }
                }
            }
            
            for(auto it = r.begin(); it != r.end(); ++it){
                for(int j=0;j<n;j++){
                    matrix[*it][j] = 0;
                }
            }
            
            for(auto it = c.begin(); it != c.end(); ++it){
                for(int j=0;j<m;j++){
                    matrix[j][*it] = 0;
                }
            }
        }
    };
    		cs
    • 이 방법은 전체 matrix를 탐방하며 값을 바꿔주는 것이 아니라, row나 column이 0인 경우에 해당하는 값만 값을 바꿔준다.
    • 7~8번째 : 0을 가지는 row, column을 저장하기 위한 배열을 만든다. 이때 중복으로 값이 들어갈 수 있으므로 set을 이용하여 만들었다.
    • 10~17번째 : 0에 해당하는 row, column을 set에 넣어줬다.
    • 19~23번째 : 위에서 만든 row set을 이용하여, matrix의 값을 바꿔준다.
      • ex. {1,5, 9}가 row set에 있다면 1, 5, 9번째 row에 해당하는 column들을 반복문으로 순회하면서 matrix를 0으로 바꿔준다.
    • 25~29번째 : 위와 동일하다.

    Runtime: 24 ms, faster than 85.54% of C++ online submissions for Set Matrix Zeroes.

    Memory Usage: 13.8 MB, less than 60.55% of C++ online submissions for Set Matrix Zeroes.

    두 방법 다 결과는 위와 동일하게 나왔다.






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고