문제
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1
관련있는 주제
Array, Hash Table, Matrix
아이디어
행이든 열이든 0이 존재한다면 그 행/열은 모두 0으로 바뀌어야 한다.
in place 방식을 사용해야 하니 같은 크기의 m x n 을 만들어서 사용할 수는 없다.
그래서 행, 열에 해당하는 Set() 를 만들어두고 0이 존재하는 행, 열의 인덱스를 기록한뒤, 모든 값을 순회하며 두가지 set 에 하나라도 해당한다면 값을 0으로 치환하는 시간복잡도 O(n^2) 방식으로 풀이했다.
코드
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
let xSet = new Set();
let ySet = new Set();
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === 0) {
xSet.add(j);
ySet.add(i);
}
}
}
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (xSet.has(j) || ySet.has(i)) matrix[i][j] = 0;
}
}
};
O(n^2) 인데도 runtime 이 나쁘지 않았다.
우선 이 in-place 라는 용어를 자료구조에서 처음 접해본 이후 알고리즘 문제에서 물어보는 유형을 처음 보게 되었다.
in-place Algorithm
In-place 하지 않은 알고리즘은 n 길이의 리스트를 정렬시 n 만큼의 메모리보다 더 많은 메모리 공간을 할당하니 이런 알고리즘은 공간복잡도가 높다.
not in-place sorting algorithm 예시Merge Sort
Counting Sort
Radix Sort
Bucket Sort
다음은 non-in-place algorithm 을 사용한 배열을 거꾸로뒤집는 코드이다.
<script>
// An Not in-place Javascript program
// to reverse an array
/* Function to reverse arr[]
from start to end*/
function reverseArray(arr,n)
{
// Create a copy array
// and store reversed
// elements
let rev = new Array(n);
for (let i = 0; i < n; i++)
rev[n - i - 1] = arr[i];
// Now copy reversed
// elements back to arr[]
for (let i = 0; i < n; i++)
arr[i] = rev[i];
}
// Driver code
let arr=[1, 2, 3, 4, 5, 6];
let n = arr.length;
reverseArray(arr, n);
// This code is contributed by rag2127
</script>
이 경우 시간복잡도는 O(n) 이 된다. 또한 추가 공간이 필요하니 공간복잡도는 O(n) 이 된다.
in-place 알고리즘이란 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘이다.
통상적으로 공간복잡도는 O(logn) 이고 O(n) 이 될 때도 있다.
in-place sorting algorithm 예시Insertion Sort
Selection Sort
Bubble Sort
Shell Sort
Heap Sort
Quick Sort
다음은 in-place algorithm 을 사용한 배열을 거꾸로뒤집는 코드이다.
<script>
// An in-place Javascript program
// to reverse an array
function __(x,y)
{
return x;
}
/* Function to reverse arr[]
from start to end*/
function reverseArray(arr,n)
{
for (let i = 0; i < n / 2; i++)
arr[i] = __(arr[n - i - 1],
arr[n - i - 1] = arr[i]);
}
// Driver code
let arr=[1, 2, 3, 4, 5, 6];
let n = arr.length;
reverseArray(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
코드 출처 : https://www.geeksforgeeks.org/in-place-algorithm/
위의 코드를 실행되는 순서가 잘 이해가 되지 않아서 디버깅을 해봤다. 특히
function __(x,y) {
return x;
}
///
arr[i] = __(arr[n - i - 1], (arr[n - i - 1] = arr[i]));위의 코드를 실행하는 상황에서 arr 가 어떻게 변하는지 확인해봤다.
디버깅을 해보니 배열의 첫번째 인덱스와 마지막 인덱스의 값을 서로 교환하고 있었다. 그래서 궁금했던 것은 다음의 arr[n - i - 1], (arr[n - i - 1] = arr[i]) 가 있을 때 두번째에서 새로운 값 arr[i] 가 arr[n-i-1] 에 할당되었는데 첫번째의 arr[n - i - 1] 에도 해당 변경점이 반영되는지가 궁금했다.
false 가 나오는 것을 보면 익명함수의 두 인자는 다른 값을 받아오고 있음을 알 수 있다. 즉, 두번째 인자에서 발생한 변경점은 첫번째 인자에 반영되지 않았음을 알 수 있다.
혹시 인자가 원시값이라 인자로 전해진 각각은 독립적으로 동작하는것인지 배열에 참조값을 넣어 다시 실행해봤다.
function __(x, y) {
return x;
}
/* Function to reverse arr[]
from start to end*/
function reverseArray(arr, n) {
for (let i = 0; i < n / 2; i++)
arr[i] = __(arr[n - i - 1], (arr[n - i - 1] = arr[i]));
}
let array = [{ a: 1 }, { a: 2 }, { a: 3 }, { a: 4 }];
reverseArray(array, array.length);
참조값이어도 in-place 방식의 교환이 가능한 것 같다.
이미지 출처 : 모던 자바스크립트 Deep Dive
인수는 값으로 평가될 수 있는 표현식이어야 한다.
자바스크립트에서 함수가 호출되면 함수 몸체 내에서 암묵적으로 매개변수가 생성되고 일반 변수와 마찬가지로 undefined 로 초기화된 이후 인수가 순서대로 할당된다.
매개변수는 함수 몸체 내부에서만 참조할 수 있고 함수 몸체 외부에서는 참조할 수 없다. 매개변수의 스코프는 함수 내부이다.
function changeVal(primitive, obj){
primitie += 100;
obj.name = 'Kim';
}
// 외부 상태
var name = 100;
var person = { name: 'Lee' };
changeVal(num, person);함수를 호출하면서 매개변수에 값을 전달하는 방식을 값에 의한 호출 ( 값에 의한 전달 ), 참조에 의한 호출 ( 참조에 의한 전달 ) 로 구별해 부를 수 있다.
원시 타입 인수의 경우 직접 변경할 수 없기에 재할당을 통해 새로운 원시 값으로 교체했고 객체 타입 인수의 경우 객체는 변경 가능한 값이니 재할당 없이 직접 할당된 객체를 변경하고 있다.
이미지 출처 : 모던 자바스크립트 Deep Dive
그렇다면 위에서 in-place 를 위해 사용한 __ 라는 함수는 어떻게 동작할까?
function __(x, y) {
return x;
}
/* Function to reverse arr[]
from start to end*/
function reverseArray(arr, n) {
for (let i = 0; i < n / 2; i++)
arr[i] = __(arr[n - i - 1], (arr[n - i - 1] = arr[i]));
}일단 arr 자체는 참조값이다. 그런데 arr 내에 있는 값은 원시값이다. 위의 예시에서는 let arr=[1, 2, 3, 4, 5, 6] 를 사용중이다.
글만으로는 요약하기가 어려워 miro 를 통해 그림을 나타내봤다.
원시 값은 그 값 자체를 바꿀 수는 없고 교체할 수 있다.
참조값은 참조하고 있는 대상을 공유하니 어느 한쪽에서 수정하면 같은 대상을 참조하고 있는 모든 곳에 변경점이 공유된다.
그렇다면 위의 코드에서 arr[n - i - 1] 와 arr[n - i - 1] = arr[i] 가 같은 참조를 유지하고 있는지가 궁금하다.
애초에 같은 arr[n - i - 1], arr[n - i - 1] 를 인자로 전달한다면?
완전히 같은 참조값을 전달하니 동일한데 참조값이 바뀌었으니 당연히 false 라고 뜬다.
뻘짓을 한 느낌이긴 한데 함수의 인자에 할당연산자가 있을때 각각의 인자는 독립적으로 동작하는 것 같다. 그래서 두번째 인자에 변화가 있어도 첫번째 인자와는 무관했던 것으로 보인다.
이걸 어떻게 검색해봐야 할지 몰라서 구체적인 원리는 아직 잘 모르겠다..
개선
음.. In-place 에 대해 다시 조사를 해보니 내 코드는 In-place 방식이 아닌 것 같다.
코드를 개선할 수 있는 방법을 찾다가 다음과 같은 아이디어가 떠올랐다.
-
먼저 O(m) 으로 row 를 돌며 Array.includes(0) 이 true 라면 row.fill(0) 으로 해당 row 를 모두 0으로 교체한다. 이때 0 이 존재했던 x index 를 xSet 에 중복을 제거하여 저장한다.
-
in-place 방식으로 arr 의 x, y 값을 바꾼다.
-
전환된 matrix 에서 O(n) 으로 row 를 돌며 해당 row 의 index 가 xSet 에 xSet.has(idx) 를 만족한다면 해당 row 를 row.fill(0) 으로 교체한다.
-
in-place 방식으로 다시 arr 의 x, y 값을 바꾼다.
그런데 이 방식도 1번에서 x index 를 찾을때 O( m x n ) 이 나온다.
다른 풀이를 봤을때 in-place 방식이 명확하게 적용된 것 같지는 않아서 in-place 방식의 풀이를 하기에 좋은 문제는 아닌 것 같다...
참고 레퍼런스
blog
Stable Sort, inplace algorithm이란? 왜 중요한가?
reference
In-place-algorithm - geeksforgeeks.org
