[1주차] 189. Rotate Array

https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150 

 

문제

주어진 nums 배열을 오른쪽으로 k 만큼 회전시켜라. 단 k >= 0 이다.

 

풀이

보자마자 LinkedList를 이용한 Queue 자료구조가 생각났고 해결했다.

좀더 직관적으로 알아볼 수 있게 Deque를 사용했다.

fun rotate(nums: IntArray, k: Int): Unit {
    val queue: Deque<Int> = LinkedList()
    nums.forEach {
        queue.addLast(it)
    }

    repeat(k % nums.size) {
        queue.addFirst(queue.removeLast())
    }

    for (i in nums.indices) {
        nums[i] = queue.removeFirst()
    }
}

 

queue에 배열을 복사하는데 O(n), 배열을 1회 회전하는데 O(1), k번 반복하는데 O(n), 마지막으로 결과를 원본 배열에 복사하는데 O(n) 이므로 시간복잡도는 O(n)이다.

nums.size만큼 queue를 복사하므로 공간복잡도는 O(n)이다.

 

k % nums.size 번 반복하는 이유:

배열을 nums.size 만큼 회전하면 원본 배열과 같다. [1,2,3] 을 3번 회전시키면 [1,2,3] 이다.

즉, 4번, 7번, 10번... 등의 회전은 1번 회전과 결과가 동일하다. 그러므로 k 를 nums.size로 모듈로 연산하면 조금 더 최적화를 할 수 있다. 물론 시간복잡도는 동일하게 O(n) 이다.

 

 

 

Could you do it in-place with O(1) extra space?

 

 

음... 문제 밑에 달려있는 Follow Up. 항상 이게 참 골때리는 것 같다.

temp 정수 변수 하나를 두고, 로테이션을 돌리는 방법을 떠올렸다. 로테이션을 한 번 돌리는데 n번 스왑하고, k번 반복하기 때문에 시간복잡도는 O(n^2) 이지만 공간복잡도는 O(1) 이므로 만족한다.

fun rotate(nums: IntArray, k: Int): Unit {
    repeat(k % nums.size) {
        var prev = nums[0]
        for (i in 1..nums.lastIndex) {
            val temp = nums[i]
            nums[i] = prev
            prev = temp
        }
        nums[0] = prev
    }
}

 

 

타 솔루션 참고

시간복잡도 O(n), 공간복잡도 O(1) 알고리즘이 있었다.

fun rotate(nums: IntArray, k: Int): Unit {
    reverseIntArray(nums, 0, nums.lastIndex)
    reverseIntArray(nums, k % nums.size, nums.lastIndex)
    reverseIntArray(nums, 0, k % nums.size - 1)
}

private fun reverseIntArray(arr: IntArray, start: Int, end: Int) {
    var i = start
    var j = end
    while (i <= j) {
        val temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
        i++
        j--
    }
}

특이한 규칙을 이용하여 문제를 푸는 모습이다.

[1,2,3,4,5] 배열을 2 번 회전하면 결과는 [4,5,1,2,3] 이다. 이 결과는 다음과 같은 과정을 통해 만들 수 있다.

• 전체 배열을 뒤집는다. - [5,4,3,2,1]
• 0부터 k-1 인덱스까지만 뒤집는다. - [4,5,3,2,1]
• k인덱스부터 마지막 인덱스까지만 뒤집는다. - [4,5,1,2,3]

 

뒤집는데 O(n), 뒤집는 과정을 3번 고정으로 반복하므로 시간복잡도는 O(n)이다.

 

문제를 단순히 시뮬레이션 하는 것도 좋지만, 숨겨진 수학적 규칙을 찾아내서 하는게 훨씬 세련되게 보인다.

물론 그게 매우 어렵다는게 문제지