리트코드 994 Rotting Oranges - Kotlin 타입에 따른 시간 단축 팁

https://leetcode.com/problems/rotting-oranges/description/

 

문제 풀이

 

이 문제는 matrix 탐색을 구현하는 간단한 문제입니다.

 

 

위 생각에 따라 작성한 답안은 다음과 같습니다.

 

 

class Solution {

    private val diff = listOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)

    fun orangesRotting(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid.first().size
        var rotCount = 0
        val fresh = ArrayDeque<Pair<Int, Int>>()

        for ((y, row) in grid.withIndex()) {
            for ((x, org) in row.withIndex()) {
                if (org == 1) {
                    fresh.add(y to x)
                } else if (org == 2) {
                    rotCount++
                }
            }
        }
        if (fresh.isNotEmpty() && rotCount == 0) {
            return -1
        }
        var time = 0

        while (fresh.isNotEmpty()) {
            var freshCount = fresh.size
            for (i in 0 until freshCount) {
                val (y, x) = fresh.removeFirst()
                // 네 방향 탐색
                var isRotted = false
                for ((dy, dx) in diff) {
                    val ny = y + dy
                    val nx = x + dx
                    if (ny in 0 until m && nx in 0 until n && grid[ny][nx] in 2..(time + 2)) {1
                        // 이번에 썩은 오렌지가 인접한 신선한 오렌지에 영향을 주지 않도록 2 + 썩은 시간으로 표시
                        grid[y][x] = time + 3
                        isRotted = true
                        break
                    }
                }
                if (!isRotted) {
                    fresh.add(y to x)
                }
            }
            if (fresh.size == freshCount) {
                return -1
            }
            time++
        }

        return time
    }
}

 

저는 신선한 오렌지의 인근에 썩은 오렌지가 있는 것을 확인했는데, 썩은 오렌지 인근에 신선한 오렌지가 있는 것을 확인하는 것이 더 효율적입니다. 신선한 오렌지는 썩을 때까지 queue에 존재하여 불필요한 탐색을 반복하지만, 썩은 오렌지는 더 이상 영향을 줄 수 없는 경우 queue에서 삭제되기 때문입니다.

 

class Solution {

    private val diff = listOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)

    fun orangesRotting(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid.first().size
        var freshCount = 0
        val rotted = ArrayDeque<Pair<Int, Int>>()

        for ((y, row) in grid.withIndex()) {
            for ((x, org) in row.withIndex()) {
                if (org == 1) {
                    freshCount++
                } else if (org == 2) {
                    rotted.add(y to x)
                }
            }
        }
        if (freshCount == 0) {
            return 0
        } else if (rotted.isEmpty()) {
            return -1
        }
        var time = -1 // 더 이상 썩을 오렌지가 없더라도 한 번 더 순회하므로 0 대신 -1

        while (rotted.isNotEmpty()) {
            var rottedCount = rotted.size
            for (i in 0 until rottedCount) {
                val (y, x) = rotted.removeFirst()
                // 네 방향 탐색
                for ((dy, dx) in diff) {
                    val ny = y + dy
                    val nx = x + dx
                    if (ny in 0 until m && nx in 0 until n && grid[ny][nx] == 1) {
                        grid[ny][nx] = 2
                        freshCount--
                        rotted.add(ny to nx)
                    }
                }
            }
            time++
        }
        return if (freshCount == 0) {
            time
        } else {
            -1
        }
    }
}

 

 

시간 단축 팁

 

4ms에 풀리는 코드를 보고, 제 코드와 어떤 차이가 있는지 분석해봤습니다.

 

import java.util.*

class Solution2 {
    fun orangesRotting(grid: Array<IntArray>): Int {
        return bfs(grid)
    }

    fun bfs(grid: Array<IntArray>): Int {
        val rows = grid.size
        val cols = grid[0].size
        val directions = arrayOf(
            intArrayOf(1, 0), // jos
            intArrayOf(-1, 0), // sus
            intArrayOf(0, 1), // dreapta
            intArrayOf(0, -1) // stânga
        )
        val queue: Queue<Pair<Int, Int>> = LinkedList()
        var freshOranges = 0
        for (i in 0 until rows) {
            for (j in 0 until cols) {
                when (grid[i][j]) {
                    2 -> queue.add(Pair(i, j))
                    1 -> ++freshOranges
                }
            }
        }
        if (freshOranges == 0) return 0
        var minutes = 0

        while (queue.isNotEmpty()) {
            val size = queue.size
            var infected = false
            for (i in 0 until size) {
                val (row, col) = queue.poll()

                for (dir in directions) {
                    val newRow = row + dir[0]
                    val newCol = col + dir[1]
                    if (newRow in 0 until rows && newCol in 0 until cols && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2
                        queue.add(Pair(newRow, newCol))
                        --freshOranges
                        infected = true
                    }
                }
            }
            if (infected) ++minutes
        }

        return if (freshOranges == 0) minutes else -1
    }
}

 

 

1. listOf 대신 arrayOf 사용하기

 

네 방향의 움직임을 저장한 diff 변수를 listOf 대신 arrayOf로 변경해 시간을 절반 단축시킬 수 있었습니다.

 

private val diff = arrayOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)

 

2. ArrayDeque 지양하기

 

썩은 오렌지를 저장하는 rotted의 타입을 ArrayDeque 대신 Queue 타입의 LinkedList로 변경해 시간을 절반 단축시킬 수 있었습니다. 자바 타입이기 때문에 java.util import가 필요합니다.

Stack과 Queue를 동시에 사용할 수 있는 ArrayDeque를 즐겨 사용했는데, 타입에 따라 구분해서 사용해야 함을 배웠습니다.

 

import java.util.*

val rotted: Queue<Pair<Int, Int>> = LinkedList()

 

 

마무리 & 변경된 코드

 

알고리즘이 아닌 타입에 따른 시간 차이로 코테에서 떨어지면 억울할 것입니다. 특히 프로그래머스는 타입에 따른 시간차이가 더 심한데, 아래 블로그 글을 확인해주세요.

https://dodobest.tistory.com/96

프로그래머스 시간 측정 오류와 H-Index 문제

 

import java.util.*

class Solution {

    private val diff = arrayOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)

    fun orangesRotting(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        var freshCount = 0
        val rotted: Queue<Pair<Int, Int>> = LinkedList()

        for (y in 0 until m) {
            for (x in 0 until n) {
                when (grid[y][x]) {
                    2 -> rotted.add(y to x)
                    1 -> freshCount++
                }
            }
        }
        if (freshCount == 0) {
            return 0
        } else if (rotted.isEmpty()) {
            return -1
        }
        var time = -1 // 더 이상 썩을 오렌지가 없더라도 한 번 더 순회하므로 0 대신 -1

        while (rotted.isNotEmpty()) {
            val rottedCount = rotted.size
            for (i in 0 until rottedCount) {
                val (y, x) = rotted.poll()
                // 네 방향 탐색
                for ((dy, dx) in diff) {
                    val ny = y + dy
                    val nx = x + dx
                    if (ny in 0 until m && nx in 0 until n && grid[ny][nx] == 1) {
                        grid[ny][nx] = 2
                        freshCount--
                        rotted.add(ny to nx)
                    }
                }
            }
            time++
        }
        return if (freshCount == 0) {
            time
        } else {
            -1
        }
    }
}