[LeetCode] 189. Rotate Array - Java

Rotate Array - LeetCode

 

문제

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

 

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 <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

 

주어진 배열 nums를 k 만큼 오른쪽으로 회전하는 문제이다.

 

---

 

내 풀이

import java.util.*;
class Solution {
    public void rotate(int[] nums, int k) {

        int n = nums.length;
        k = k%n; // k가 n보다 큰 경우에 대비

        Queue<Integer> queue = new LinkedList<>();

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

큐를 사용해서 풀었다.

배열을 순회하며서 모든 요소들을 큐에 담는다.

배열의 인덱스 i가 k 보다 작을 경우, 해당 위치에는 n - k + i 에 있는 요소들이 삽입된다.

같거나 클 경우 큐에서 요소를 poll 한 뒤 해당 위치에 삽입한다.

 

• 시간복잡도 : O(n)
• 공간복잡도 : O(n) - 큐를 사용하면서 메모리가 추가적으로 사용

 

간단한 오른쪽 회전을 구현하는데에 꽤 복잡한 방법을 사용하는 풀이이고, 메모리 사용면에서 비효율적인 코드라는 생각이 들었다.

생각해보니까 굳이 큐까지 사용할 필요 없이 nums 배열을 복사한 배열을 만들었어도 됐을 것 같은데 어쨌든 비효율적인건 똑같다.

 

---

 

다른 사람의 풀이

import java.util.*;
class Solution {
    public void rotate(int[] nums, int k) {

        int n = nums.length;
        k = k % n;

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

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

Input : nums = [1,2,3,4,5,6,7], k = 3

(1) 배열 전체를 뒤집는다.

• nums = [7, 6, 5, 4, 3, 2, 1]

(2) 0 부터 k-1 까지의 요소들 (앞부분)을 다시 뒤집는다.

• nums = [5, 6, 7, 4, 3, 2, 1]

(3) k 부터 n-1 까지의 요소들 (뒷부분)을 다시 뒤집는다.

• nums = [5, 6, 7, 1, 2, 3, 4]

 

요소 하나하나씩 회전시키는것이 아니라 범위를 잡아서 영역만큼 뒤집는 방식으로 구현하는 것은 생각하지도 못한 방식이라 놀라웠다.

추가적인 메모리 사용이 없기 때문에 공간복잡도는 O(1)이 된다.