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

2023. 5. 27. 21:05·알고리즘/알고리즘
반응형

문제

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(","))
    }
}
반응형

'알고리즘 > 알고리즘' 카테고리의 다른 글

[Kotlin] 행렬에서 특정 원소에 0이 포함되면 해당 원소의 행과 열 모두 0으로 만들기  (0) 2023.05.28
[Kotlin] String 압축하기 : 반복되는 문자 압축하기  (0) 2023.05.26
[Kotlin] 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인  (0) 2023.05.25
[Kotlin] String이 Palindrome Permutation인지 확인하기  (0) 2023.05.24
[Kotlin] 공백을 "%20"으로 대체해 Url로 만들기  (0) 2023.05.23


'알고리즘/알고리즘' 카테고리의 다른 글
  • [Kotlin] 행렬에서 특정 원소에 0이 포함되면 해당 원소의 행과 열 모두 0으로 만들기
  • [Kotlin] String 압축하기 : 반복되는 문자 압축하기
  • [Kotlin] 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인
  • [Kotlin] String이 Palindrome Permutation인지 확인하기
심플코드
심플코드
프로그래밍을 어렵지 않게 풀어서 설명하는 기술 블로그
    반응형
  • 심플코드
    심플코드
    심플코드
  • 전체
    오늘
    어제
    • 분류 전체보기 (96)
      • 안드로이드를 위한 Coroutines (2)
      • Unit Testing (19)
      • GitHub Actions (0)
      • 공식 문서 번역 (35)
        • Coroutines 공식 문서 (35)
      • 알고리즘 (7)
        • Kotlin 자료구조 (0)
        • 알고리즘 (7)
        • Kotlin으로 구현하는 자료구조 (0)
      • 코딩 테스트 (0)
      • Deep Learning (0)
      • Machine Learning Math (17)
        • Linear Algebra (17)
      • ML (0)
      • Docker (15)
      • Kubernetes (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

    • 코틀린 코루틴의 정석 책 출간 소식
  • 인기 글

  • 태그

    컨테이너
    mockito
    Docker
    Coroutines Flow
    TensorFlow
    numpy
    Coroutines Channel
    코루틴 채널
    coroutine
    코루틴 Flow
    Coroutines
    Coroutines Context
    Kotlin
    도커
    unit testing
    코루틴
    pytorch
    Machine Learning
    unit test
    junit
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
심플코드
[Kotlin] Matrix 90도 회전시키기 : Matrix Rotation
상단으로

티스토리툴바