[OJ.leetcode] set-matrix-zeroes

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

 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) 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 알고리즘은 은 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; } } }