[LeetCode] 73. Set Matrix Zeroes (Java, In-place)

문제

 

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

Set Matrix Zeroes - LeetCode

 

풀이

 

난이도: Medium 

 

단순히 새로운 2차원 배열에 값을 복사해 넣으면서 만들면 굉장히 쉽지만 O(mn)의  공간 복잡도가 소요된다.

 

공간 복잡도를 최적화하는 다른 방법으로는 각 row와 column이 0으로 채워져야하는지 여부를 O(n + m) 공간으로 저장은 가능하지만, 문제에서는 in-place 알고리즘을 요구한다.

in-place는 리스트 정렬과 같이 원소들의 변경할때 추가적인 메모리 공간 없이 진행되는 알고리즘을 의미한다.

 

이번 문제를 inplace 알고리즘을 해결하기 위해서는 O(n + m)의 공간 복잡도로 구현한 아이디어와 비슷하게 진행한다.

바로 해당 row나 column이 0이 되야하는 지의 여부를 가장 앞의 원소를 0으로 바꿈으로써 표현하는 것이다.

 

예를 들며  다음과 같이 중간에 0이 있다면 해당 row의 0번째 원소를 0으로, column의 0번째 요소를 0으로 바꾸어 준다.

 

모든 원소에서 이를 진행했다면 0번째 원소가 0인 줄은 모두 0으로 바꾸어 주면 된다.

단, (0,2) 번째 원소가 0이기 때문에 (0,0)인 첫 원소가 0으로 바꾼다면 이는 0번째 row와 0번째 column을 모두 0으로 만들어 오답이 된다.

 

따라서 0번째 row와 0번째 column 만 따로 해당 줄이 0으로 바뀌는지 여부를 boolean값으로 저장해야 한다.

 

이런 구현은 추가적인 공간을 사용은 하지만 O(1)으로 최적화할 수 있다.

 

코드