문제

nums라는 배열이 존재할 때 k 스탭만큼 오른쪽으로 회전시키는 문제이다. 이때, 마지막 인덱스의 원소의 다음 스탭은 처음 원소가 된다.

첫번째 풀이

첫 풀이는 가장 쉬운 방법으로 풀어봤다. 임시 배열 temp를 선언하고 이 배열에 회전한 결과를 저장한다. 그 다음 temp 배열의 값을 다시 nums 배열에 저장한다. 이 풀이는 시간복잡도는 $O(2n)$이며 공간복잡도는 $O(n)$이 된다.

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

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

두번째 풀이

이번 풀이에서는 k < nums.length라는 조건이 없기 때문에 k %= nums.length로 만들어 조금 더 간단하게 만들었다. 또한 k == 0이면 rotate을 하지 않기때문에 반복문을 실행하기전에 함수를 종료하도록 개선했다. 기존의 시간복잡도가 $O(2n)$이었는데 Queue 자료구조를 사용해 $O(n)$으로 반복횟수를 줄여보았다.

배열 뒤의 k개는 맨 앞으로 옮기며 맨 앞의 k개 값을 유지하기 위해 Queue를 사용하였다.

class Solution {
    public void rotate(int[] nums, int k) {
        Queue<Integer> queue = new ArrayDeque<>();
        int n = nums.length;
        k %= n;

        if (k == 0) {
            return;
        }

        for (int i = 0; i < n; i++) {
            queue.add(nums[i]);

            if (i < k) {
                nums[i] = nums[i + (n - k)];
            } else {
                nums[i] = queue.poll();
            }
        }
    }
}

반복횟수를 n번 줄이긴 했지만 객체(자료구조)를 생성하여 사용하다보니 오히려 실행시간이 오래걸리게 나온 것같다.

Solution을 보고..

Solution을 보기전까지 내가 생각했던 풀이는 말 그대로 각 원소를 k칸씩 옮기는 풀이밖에 생각을 못했다. 하지만 Solution에는 다들 내가 전혀 생각하지 못한 방법으로 풀었다. 방법은 다음과 같다.

1. left(0부터, left++), right(nums.length - 1부터, right--) 인덱스를 left < right일때까지 값을 서로 바꾼다.
2. 1번의 결과에서 left = 0, right = k - 1로 시작해 1번과 동일한 과정을 수행한다.
3. 2번 결과에서 left = k, right = nums.length - 1로 시작해 1번과 동일한 과정을 수행한다.

예를들어 nums = [1,2,3,4,5,6,7], k = 3이면

1번 과정 후 : nums = [7,6,5,4,3,2,1]
2번 과정 후 : nums = [5,6,7,4,3,2,1]
3번 과정 후 : nums = [5,6,7,1,2,3,4]

와 같이 수행된다. 이를 코드로 작성하면 다음과 같다.

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

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

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            start += 1;
            end -= 1;
        }
    }
}

이 풀이 시간복잡도는 2 * n(= nums.length)번 반복하므로 $O(n)$이며 nums.length가 얼마든 스택에 3번만 쌓이므로 $O(1)$이 된다.