[Kotlin] Leetcode 189. Rotate Array

Problem

배열이 주어졌을 때, 배열을 오른쪽으로 k번 회전시킵니다. 여기서 k는 음수가 아닙니다.

 

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

 

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

 

Follow up:

• 가능한 한 많은 솔루션을 찾아보세요. 이 문제를 해결하는 방법에는 최소한 세 가지가 있습니다.
• O(1) extra space로 제자리에서 할 수 있을까요?

Solution

1. Time O(n^2); 

 

단순하게 k % nums.size를 하면 k가 배열의 크기를 넘는 경우를 제외하고 몇번이 남는지를 구할 수 있다. 

count만큼 뒤에서부터 앞으로 nums의 값을 변경한다. 

nums = [1 2 3 4] 이면 [2 3 4 1]이 되는 것인데 이 것을 k번 반복한다. for문이 2개이므로 O(n^2)이 된다.

//time-O(n^2); n is size of array
fun rotate(nums: IntArray, k: Int) {
    val count = k % nums.size
    for (i in 1..count) {
        val last = nums[nums.lastIndex]
        for (j in nums.lastIndex downTo 1) {
            nums[j] = nums[j - 1]
        }
        nums[0] = last
    }
}

 

2. Time O(n), Space O(n)

 

더 똑똑하게 하는 방법은 for문을 한번만 사용해서 하는 것이다.

똑같이 k % nums.size를 하여 몇번 움직일지 정하고 새로운 array을 nums.size만큼 선언한다. (a)

 

a에 배열에 nums[i]가 이동하면 어디로 갈지를 계산하여 저장한다. O(n)

그 다음 다시 nums[i]에 a[i]를 저장하면 nums[i]가 변경된다. 

 

a라는 배열을 nums.size만큼 만들었기 때문에 공간 복잡도는 O(n)이 된다.

//time-O(n), space-O(n); n is size of array
fun rotate(nums: IntArray, k: Int) {
    val rotation = k % nums.size
    val a = IntArray(nums.size)
    for (i in nums.indices) {
        a[(i + rotation) % nums.size] = nums[i]
    }
    for (i in a.indices) {
        nums[i] = a[i]
    }
}

 

3. Time O(n), Space O(1)

 

그럼 이번에는 공간을 새로 할당하지 말고 돌리는 방법은 무엇이 있을까?

 

아까와 동일하게 index를 구하는 것은 동일하다. (currIndex + rotation ) % nums.size

 

여기서 추가된 것은 temp인데 여기에 nums[nextIdx]를 저장해 놓고

현재의 값을 nums[nextIdx]에 저장한다. 그러고 나서 temp 값을 nums[startIdx]에 저장하면 배열의 값이 swap된다.

 

swap count를 별도로 두어서 swap이 nums.size만큼 이루어지면 모든 배열이 바뀐 것이고 결과를 return한다.

아니면 계속 startIdx와 currIdx가 같아질 때까지 배열을 교환해주고 같아질때까지 swap이 배열의 size만큼 교체가 되지 않았으면 startIdx를 다음 배열로 이동한다. 

//time-O(n), space-O(1); n is size of array
fun rotate(nums: IntArray, k: Int) {
    var rotation = k % nums.size
    var swap = 0
    var startIdx = 0
    while (startIdx < nums.size) {
        var currIdx = startIdx
        var prev = nums[startIdx]
        do {
            val nextIdx = (currIdx + rotation) % nums.size
            val temp = nums[nextIdx]
            nums[nextIdx] = prev
            prev = temp
            currIdx = nextIdx
            swap++
            if (swap == nums.size) return
        } while (startIdx != currIdx)
        startIdx++
    }
}

 

O(1) 해답은 좀 복잡한 코드이지만 언젠가 써먹을 날이 올지도 모른다!