[LeetCode / Kotlin] Spiral Matrix

문제

Given an m x n matrix, return all elements of the matrix in spiral order.

 

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

 

 

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

 

나의 풀이

1. 각 방향 별, 움직임을 정의한다.

2. 이미 탐색했던곳을 검증하기 위한 MARKING_NUMBER를 지정. (제약사항에서 나올 수 없는 숫자인 111로 임의 지정.)

 

class Solution {

    private val MARKING_NUMBER = 111

    fun spiralOrder(matrix: Array<IntArray>): List<Int> {

        val maxM = matrix.lastIndex
        if (maxM < 0) {
            return listOf()
        }
        val maxN = matrix[0].lastIndex
        if (maxN < 0) {
            return listOf()
        }

        val tmp = matrix.clone()
        var d = Direction.RIGHT
        var m = 0
        var n = 0

        val res = IntArray((maxM + 1) * (maxN + 1)).apply {
            this[0] = tmp[0][0]
            tmp[0][0] = MARKING_NUMBER
        }

        for (i in 1..res.lastIndex) {
            val expectedCoord = go(m, n, d)
            val em = expectedCoord[0]
            val en = expectedCoord[1]

            when(d) {
                Direction.RIGHT -> {
                    // 벗어나는곳 or 이미 갔던곳
                    if (en > maxN || tmp[em][en] == MARKING_NUMBER) {
                        m = em + 1
                        n = en - 1
                        d = Direction.DOWN
                    } else {
                        m = em
                        n = en
                    }
                }
                Direction.LEFT -> {
                    if (en < 0 || tmp[em][en] == MARKING_NUMBER) {
                        m = em - 1
                        n = en + 1
                        d = Direction.UP
                    } else {
                        m = em
                        n = en
                    }
                }
                Direction.UP -> {
                    if (em < 0 || tmp[em][en] == MARKING_NUMBER) {
                        m = em + 1
                        n = en + 1
                        d = Direction.RIGHT
                    } else {
                        m = em
                        n = en
                    }
                }
                Direction.DOWN -> {
                    if (em > maxM || tmp[em][en] == MARKING_NUMBER) {
                        m = em - 1
                        n = en - 1
                        d = Direction.LEFT
                    } else {
                        m = em
                        n = en
                    }
                }
            }

            res[i] = tmp[m][n]
            tmp[m][n] = MARKING_NUMBER

        }

        return res.toList()
    }


    private fun go(m: Int, n: Int, direction: Direction): IntArray {
        return when(direction) {
            Direction.RIGHT -> intArrayOf(m, n + 1)
            Direction.LEFT -> intArrayOf(m, n - 1)
            Direction.UP -> intArrayOf(m - 1, n)
            Direction.DOWN -> intArrayOf(m + 1, n)
        }
    }


    enum class Direction {
        RIGHT,
        LEFT,
        UP,
        DOWN
    }
}