[Kotlin] Matrix 90도 회전시키기 : Matrix Rotation

문제

NxN Matrix가 주어졌을 때 이를 90도 회전시키는 알고리즘을 작성해라. 각 픽셀은 4bytes로 이루어져 있다.

문제 풀기 전 확인 사항

- 시작점은 [0, 0]으로 둔다.

-> [x, y] 위치는 [y, N-1-x]로 이동한다.

문제 풀이1

이런 문제는 먼저 쉬운 방식으로 풀어야 한다. 

1. 같은 크기의 Matrix를 만들어낸다.

2. [x, y] 위치의 원소를 새로운 Matrix의 [y, N-1-x] 로 이동한다.

class Solution() {
    fun rotate(matrix: Array<IntArray>): Array<IntArray> {
        val SIZE_N = matrix.size
        val newMatrix = Array(SIZE_N) { IntArray(SIZE_N) }

        matrix.forEachIndexed { rowIndex, intArray ->
            intArray.forEachIndexed { columnIndex, intValue ->
                newMatrix[columnIndex][SIZE_N - 1 - rowIndex] = intValue
            }
        }

        return newMatrix
    }
}

복잡도

Matrix의 총 원소 수를 M이라 했을 때

시간 복잡도 : O(M) - M만큼 원소를 모두 조회해야 하므로

공간 복잡도 : O(M) - 새로운 공간을 M 만큼 만들었으므로

문제 풀이2

이 방법은 추가 공간을 더 사용하지 않고도 풀 수 있는 방법이 있다.

바로 하나의 tmp 공간을 두고 회전을 시키는 것이다. [r, c]라는 노드가 있으면

1. tmp = [N-c-1, r] 저장

2. [r, c] -> [c, N-r-1] -> [N-r-1, N-c-1] -> [N-c-1, r] 노드를 90도씩 돌림
를 하면된다.

class Solution2() {
    // size = N, rowIndex = r, columnIndex = c
    // [r, c] -> [c, N-r-1] -> [N-r-1, N-c-1] -> [N-c-1, r]
    // tmp = [N-c-1, r]


    fun rotate(matrix: Array<IntArray>): Array<IntArray> {
        val SIZE_N = matrix.size
        var tmpNode = 0

        matrix.forEachIndexed { rowIndex, intArray ->
            if(rowIndex >= SIZE_N/2) return@forEachIndexed
            for(columnIndex in rowIndex..(SIZE_N-rowIndex)-2) {
                tmpNode = matrix[SIZE_N-1-columnIndex][rowIndex]
                matrix[SIZE_N-columnIndex-1][rowIndex] = matrix[SIZE_N-rowIndex-1][SIZE_N-columnIndex-1]
                matrix[SIZE_N-rowIndex-1][SIZE_N-columnIndex-1] = matrix[columnIndex][SIZE_N-rowIndex-1]
                matrix[columnIndex][SIZE_N-rowIndex-1] = matrix[rowIndex][columnIndex]
                matrix[rowIndex][columnIndex] = tmpNode
            }
        }

        return matrix
    }
}

복잡도

Matrix의 총 원소 수를 M이라 했을 때

시간 복잡도 : O(M) - M만큼 원소를 모두 조회해야 하므로

공간 복잡도 : O(1) - 새로운 공간을 tmp 하나만큼 만들었으므로

테스트 케이스

이런 경우는 테스트 케이스를 하나만 빠르게 돌려보자.

fun main() {
    val solution = Solution2()
    val matrix = arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6), intArrayOf(7, 8, 9))
    val newMatrix = solution.rotate(matrix)
    printMatrix(newMatrix)
}

fun printMatrix(matrix: Array<IntArray>){
    matrix.forEach {
        println(it.joinToString(","))
    }
}