문제
행렬에서 특정 원소에 0이 포함되면 해당 원소의 행과 열 모두 0으로 만들기
문제 풀기 전 확인 사항
- 행렬의 최대 행과 열의 수 확인
- 원소는 모두 Int 인지 확인
문제 풀이
1. 한 번 모든 원소를 돌면서 0으로 만들어질 row index와 column index를 체크한다.
2. 체크된 index에 해당하는 row, column을 모두 0으로 만든다.
class Solution {
fun makeZero(matrix: Array<IntArray>) {
if (matrix.size == 0) return
val rowDoneArray = BooleanArray(matrix.size)
val columnDoneArray = BooleanArray(matrix[0].size)
matrix.forEachIndexed { rowIndex, intArray ->
intArray.forEachIndexed { columnIndex, intValue ->
if (intValue == 0) {
if (!rowDoneArray[rowIndex]) {
rowDoneArray[rowIndex] = true
}
if (!columnDoneArray[columnIndex]) {
columnDoneArray[columnIndex] = true
}
}
}
}
rowDoneArray.forEachIndexed { index, isZero ->
if (isZero) {
for (column in 0..matrix[0].size - 1) {
matrix[index][column] = 0
}
}
}
columnDoneArray.forEachIndexed { index, isZero ->
if (isZero) {
for (row in 0..matrix.size - 1) {
matrix[row][index] = 0
}
}
}
}
}
복잡도
Row 크기가 N Column 크기가 N일 때 복잡도는 다음과 같다.
1. 시간 복잡도 : O(N*M) : N*M번 반복해야 하므로
2. 공간 복잡도 : O(N+M) : N, M 만큼의 공간을 추가 차지하므로
테스트 케이스
fun main() {
val matrix = arrayOf(
intArrayOf(1, 2, 3, 4, 5),
intArrayOf(0, 1, 2, 3, 4),
intArrayOf(1, 0, 2, 3, 4)
)
val solution = Solution()
solution.makeZero(matrix)
printMatrix(matrix = matrix)
}
fun printMatrix(matrix: Array<IntArray>) {
matrix.forEach {
println(it.joinToString(","))
}
}
반응형
'알고리즘 > 알고리즘' 카테고리의 다른 글
[Kotlin] Matrix 90도 회전시키기 : Matrix Rotation (0) | 2023.05.27 |
---|---|
[Kotlin] String 압축하기 : 반복되는 문자 압축하기 (0) | 2023.05.26 |
[Kotlin] 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인 (0) | 2023.05.25 |
[Kotlin] String이 Palindrome Permutation인지 확인하기 (0) | 2023.05.24 |
[Kotlin] 공백을 "%20"으로 대체해 Url로 만들기 (0) | 2023.05.23 |