[LeetCode] 189. Rotate Array (in-memory)

문제

배열 nums가 주어질 때, nums의 원소들을 k 만큼 오른쪽으로 미는 코드를 작성해라.

Space complexity O(1)로 풀어보라는 추가 조건이 있으면 어려워진다.

 

예시

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4] // 반환타입 없음

조건

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

초안

k % nums.size 만큼의 공간에 기존 정보를 저장하고 하나씩 바꾸는 방식을 고안해봤는데,

이 값의 최대값이 10^5 - 1이어서 좋은 솔루션은 아니다.

 

다른 사람 코드

전체 배열을 뒤집은 후, k번째 원소를 기준으로 다시 부분을 뒤집으면 된다.

fun rotate(nums: IntArray, k: Int) {
    val rotate = k % nums.size
    reverse(nums, 0, nums.size - 1)
    reverse(nums, 0, rotate - 1)
    reverse(nums, rotate, nums.size - 1)
}

fun reverse(nums: IntArray, _start: Int, _end: Int) {
    var start = _start
    var end = _end
    while (start < end) {
        val temp = nums[start]
        nums[start] = nums[end]
        nums[end] = temp
        start++
        end--
    }
}