[LeetCode] 189. Rotate Array

문제

189. Rotate Array

코드

Deque 를 이용한 풀이

문제를 보자마자 Deque 이 생각났다. 단순히 k 번 만큼 반복문을 돌면서 맨뒤의 element 를 빼고 앞에다가 넣으면 되는 것이었다.
문제를 해결하는 것이 중요하니 일단 이 방식으로 풀었다.

class Solution {
    public void rotate(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=0;i<nums.length;i++)
            dq.add(nums[i]);

        for(int i=0;i<k;i++){
            int target = dq.pollLast();
            dq.addFirst(target);
        }
        
        
        for(int i=0;i<nums.length;i++){
            nums[i] = dq.removeFirst();
        }
    }
}

보기에는 좋지만 효율적인 코드는 아니었다. Deque 자체의 시간복잡도는 다음과 같다.

나쁜 편은 아니지만 문제를 해결한 사람들에 비해서는 하위권에 속해서 discussion을 통해 좋은 방법을 알았다.

투 포인터를 이용한 풀이

핵심 아이디어는 다음과 같다.

1. 뒤에서 k개 만큼의 원소가 앞으로 와야 한다.
2. 기존 배열을 앞에서부터 nums.length - k 개, 그 이후로 k 개로 나눈다.
3. 각 배열을 뒤집는다.
4. 두 배열을 다시 합친 후 뒤집는다.

예를들면 다음과 같다.

nums = [1,2,3,4,5,6,7], k = 3 일때, 다음의 과정을 거친다.

[1,2,3,4] [5,6,7]

[4,3,2,1] [7,6,5]

[4,3,2,1,7,6,5]

[5,6,7,1,2,3,4] --> ANSWER!

위의 과정을 코드로 바꾸면 된다.

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

        front = reverse(front);
        back = reverse(back);
        for (int i = 0; i < nums.length - k; i++)
            nums[i] = front[i];
        for (int i = 0; i < k; i++)
            nums[nums.length - k + i] = back[i];
        nums = reverse(nums);
    }

    public int[] reverse(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
        return arr;
    }
}