set-matrix-zeroes

gistfile1.txt

https://oj.leetcode.com/problems/set-matrix-zeroes/

/*
가장 간단한 in place 알고리즘은 은 for 루프를 이용, O(mn)만큼 순회하면서 처음에 0인 element는 -1 또는 아무 값으로 변경하고
그다음 다시 O(mn)만큼 순회하면서 이를 0으로 바꾸는 방법(문제의 정의에서, 나중에 바뀐 0에 해당하는 열과행은 set zero 하지 않아야 하므로

엄밀히 말해서 input에 어떤 integer 값이 들어올지 모르기 때문에 맞는 풀이는 아님.
*/


class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int marker = -999999;
        
        for(int i=0; i<matrix.size(); i++) {
            for(int j=0; j<matrix[i].size() ; j++) {
                
                if(matrix[i][j] == 0) {
                    for(int k=0 ; k<matrix[i].size(); k++) {
                        if(matrix[i][k] != 0) matrix[i][k] = marker;
                    }
                    
                    for(int l=0; l< matrix.size() ; l++) {
                        if(matrix[l][j] != 0) matrix[l][j] = marker;
                    }
                }
            }
        }
        
        for(int i=0; i<matrix.size(); i++) {
            for(int j=0; j<matrix[i].size(); j++) {
                if(matrix[i][j] == marker) matrix[i][j] = 0;
            }
        }
        
    }
};