문제

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

해결 방법 1

• k가 n보다 큰 경우가 존재할 수 있음 => n번 rotate하면 원상태로 복귀하므로 k = k % n 계산을 먼저 해줌
• nums는 0 ~ n-1까지 채워져 있는데 k번 rotate 한다면 0번째 있던 수는 k번째로 가게 되고, n-k번째 있던 수가 0번째로 오게 됨
• 이를 이용하여 result 배열에 n-k ~ n-1 번째 수들을 먼저 채워주고 0 ~ n-k-1 번째 수들을 채워주면 됨

코드

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n];
        int idx = 0;
        
        k %= n;
        for (int i = n - k ; i < n ; i ++) {
            result[idx ++] = nums[i];
        }
        for (int i = 0 ; i < n - k ; i ++) {
            result[idx ++] = nums[i];
        }

        for(int i = 0 ; i < n ; i ++) {
            nums[i] = result[i];
        }
    }
}

결과

해결 방법 2

• nums = [1,2,3,4,5,6,7], k = 3 이라고 가정
• 뒤에 있던 [5,6,7]이 앞으로 오고, [1,2,3,4]가 뒤로 가야 함
• nums에서 [5,6,7], [1,2,3,4]를 각각 뒤집어 주면 [4,3,2,1,7,6,5] 가 되고, 이 전체를 한번 더 뒤집어 주면 [5,6,7,1,2,3,4]가 됨
• 전체를 뒤집는 과정의 시간 복잡도가 O(n/2)가 걸리므로 전체 시간 복잡도는 O(n)
• 해결 방법 1에서는 시간 복잡도가 O(2n)이고 추가 배열을 하나 더 사용했었는데 해결 방법 2는 시간, 공간 복잡도를 줄일 수 있음

코드

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;        
        k %= n;

        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start ++] = nums[end];
            nums[end --] = temp;
        }
    }
}

결과