행렬 문제

 

 

 

행렬 채우기 

 

1) set-matrix-zeroes

문제 : https://leetcode.com/problems/set-matrix-zeroes/

0이 표시된 행렬의 열과 행을 모두 0으로 바꾸는 문제이다. 

 

1. 모든 0위치를 찾아 저장하고 해당 열과 행을 전체 0으로 설정하는 방법 

시간 복잡도 : O(m x n)  + z (0의 갯수) * (O(m+n)

공간 복잡도 : 최대 O(m x n)  (0의 갯수를 따로 저장함)

class Solution {
    fun setZeroes(matrix: Array<IntArray>): Unit {
        if(matrix.size == 0) return 
        val zeros = mutableListOf<Array<Int>>()
        val v = matrix.size 
        val h = matrix[0].size 
        for(i in 0..v-1) {
            for (j in 0..h-1) {
                if(matrix[i][j] == 0) {
                    zeros.add(arrayOf(i, j))
                }
            }
        }

        for(zero in zeros) {
            checkZeroMatrix(zero[0], zero[1], matrix, v, h)
        }

    }

    private fun checkZeroMatrix(i: Int, j: Int, matrix: Array<IntArray>, v: Int, h: Int) {
        for(a in 0..h-1) {
            matrix[i][a] = 0
        }
        for (b in 0..v-1) {
            matrix[b][j] = 0 
        }
    }
}

 

2. in-place 풀이 방법 

• 1)  첫 행/열을 기준으로 삼아서 0이 있는 자리에 마킹한다. 
• 2) 나머지 셀들을 순회하며 0이 있는 칸(i, j)에서는 첫 행 / 열 에 해당하는 위치에 0으로 마킹한다.
• 3) 마킹된 행 / 열을 기준으로 0으로 설정한다. 
• 4) 첫행/열이 0이 맞다면 모두 0으로 표시한다. 

시간 복잡도 : O(m x n)

공간 복잡도 : O(1) in-place

class Solution {
    fun setZeroes(matrix: Array<IntArray>) {
        val m = matrix.size
        val n = matrix[0].size

        var firstRowZero = false
        var firstColZero = false

        // 1. 첫 행/열에 0이 있는지 확인
        for (i in 0 until m) {
            if (matrix[i][0] == 0) firstColZero = true
        }
        for (j in 0 until n) {
            if (matrix[0][j] == 0) firstRowZero = true
        }

        // 2. 0이 있는 셀의 행과 열을 첫 행/열에 마킹
        for (i in 1 until m) {
            for (j in 1 until n) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                }
            }
        }

        // 3. 마킹된 행/열을 기준으로 0 설정
        for (i in 1 until m) {
            for (j in 1 until n) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
        }

        // 4. 첫 행/열 처리
        if (firstColZero) {
            for (i in 0 until m) matrix[i][0] = 0
        }
        if (firstRowZero) {
            for (j in 0 until n) matrix[0][j] = 0
        }
    }
}

 

 

행렬 특정 순서대로 출력하기 

1) spiral-matrix 

문제 : https://leetcode.com/problems/spiral-matrix/

 

1. 행렬을 변경하면서 방문하는 방법

처음에는 while문을 사용해서 in-place 방식으로 풀었다. 

시간 복잡도 : O(m × n)

공간 복잡도 : O(m × n) (필수 공간이므로 공간 복잡도에 포함) 

// 내가 푼 방식 
class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        if(matrix.size == 0 || matrix[0].size == 0) {
            return listOf()
        }
        val answer = mutableListOf<Int>()
        val m = matrix.size
        val n = matrix[0].size
        
        val d = listOf(listOf(0, 1), listOf(1, 0), listOf(0, -1), listOf(-1, 0))
        var i = 0 
        var j = 0 
        var idx = 0

        while(matrix[i][j]!=-200) {
            answer.add(matrix[i][j])
            matrix[i][j] = -200
            var nx = i + d[idx][0]
            var ny = j + d[idx][1]
            if(nx<0 || ny<0 || nx>=m || ny>=n || matrix[nx][ny] == -200) {
                idx = (idx + 1) % 4
                nx = i + d[idx][0]
                ny = j + d[idx][1]
            }
            i = nx 
            j = ny  
            if(nx<0 || ny<0 || nx>=m || ny>=n ) {
                break
            }       
        }
        return answer.toList()
    }
}

 

 

내가 푼 방식은 인덱스 안정성에 떨어질 수 있다. 

또, while문의 수는 m*n (행렬을 모두 돌아야함) 이므로 이를 활용할 수 있다. 

class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        if(matrix.size == 0 || matrix[0].size == 0) {
            return listOf()
        }
        val answer = mutableListOf<Int>()
        val m = matrix.size
        val n = matrix[0].size
        
        val d = listOf(listOf(0, 1), listOf(1, 0), listOf(0, -1), listOf(-1, 0))
        var i = 0 
        var j = 0 
        var idx = 0
        var step = 0 

        while(step<m*n) {
            answer.add(matrix[i][j])
            matrix[i][j] = -200
            var nx = i + d[idx][0]
            var ny = j + d[idx][1]
            step ++ 
            if(nx<0 || ny<0 || nx>=m || ny>=n || matrix[nx][ny] == -200) {
                idx = (idx + 1) % 4
                nx = i + d[idx][0]
                ny = j + d[idx][1]
            }
            i = nx 
            j = ny  

        }
        return answer.toList()
    }
}

 

 

2. 경계 범위를 정하고 순회하는 방법 

시간 복잡도 : O(m × n)

공간 복잡도 : O(m × n) (필수 공간이므로 공간 복잡도에 포함) 

 // Solution 2
        val m = matrix.size 
        val n = matrix[0].size
        val result = mutableListOf<Int>()

        var top = 0
        var bottom = m-1
        var left =0 
        var right = n-1

        while(top<= bottom && left <= right) {
            for(j in left..right) result.add(matrix[top][j])
            top ++
            for(i in top..bottom) result.add(matrix[i][right])
            right --
            if(top<=bottom) {
                for(j in right downTo left) result.add(matrix[bottom][j]) 
                bottom --
            }
            if(left <= right) {
                for(i in bottom downTo top) result.add(matrix[i][left])
                left++
            }
        }
        return result 
    }

 

 

 

행렬 회전하기 

1) rotate-image

문제 : https://leetcode.com/problems/rotate-image/

 

행렬을 90도 회전하는 방법은 

Step1: Transpose ( 전치 행렬 = 행과 열을 바꿈 = (matrix[i][j] <->  matrix[j][i] ) 후 

Step2: Horizontal revers ( 좌우 반전 = 각 행을 뒤집음)을 실행하는 것이다. 

 

 

class Solution {
    fun rotate(matrix: Array<IntArray>): Unit {
        val n = matrix.size

        // Step1: Transpose 
        for (i in 0 until n) {
            for (j in i+1 until n) {
                val temp = matrix[i][j]
                matrix[i][j]= matrix[j][i]
                matrix[j][i] = temp 
            }
        }

        // Step2: horizontal reverse
        for (row in matrix) {
            row.reverse()
        }
    }
}

 

 

 

행렬 백트래킹 

 

1) word-search 

문제 : https://leetcode.com/problems/word-search

 

행렬에 주어진 문자와 일치하는 항목이 있는지 검사하는 문제이다. 

class Solution {
    fun exist(board: Array<CharArray>, word: String): Boolean {
        val m = board.size
        val n = board[0].size

        for(i in 0 until m) {
            for(j in 0 until n) {
                if(board[i][j] == word[0]) {
                    if(find(i, j, 0, board, word)) {
                        return true 
                    }
                }
            }
        }
        return false 
    }

    private fun find(i: Int, j: Int, idx: Int, board: Array<CharArray>,  word: String): Boolean {
        if(idx == word.length) {
            return true 
        }
        if (i !in board.indices || j !in board[0].indices || board[i][j] != word[idx]) {
            return false 
        }

        val temp = board[i][j]
        board[i][j] = '#'

        val result = find(i+1, j, idx+1, board, word) ||
        find(i-1, j, idx+1, board, word) ||
        find(i, j+1, idx+1, board, word) ||
        find(i, j-1, idx+1, board, word) 
        board[i][j] = temp 
        
        return result 
    }

}