[Kotlin] 행렬에서 특정 원소에 0이 포함되면 해당 원소의 행과 열 모두 0으로 만들기

문제

행렬에서 특정 원소에 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(","))
    }
}