[LeetCode] 189. Rotate Array

Problem

Given an array, 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

---

Solution

class Solution {
    public void rotate(int[] nums, int k) {
        int newK = k % nums.length;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < newK; i++)
            stack.push(nums[nums.length - 1 - i]);
        for (int i = nums.length - 1 - newK; -1 < i; i--)
            nums[i + newK] = nums[i];
        for (int i = 0; i < newK; i++) 
            nums[i] = stack.pop();
    }
}

Explanation

• 아래의 표와 같이 k의 값이 증가하여 배열의 길이와 같아지게 되면, 배열을 회전하지 않은 것과 같은 결과를 만들어낸다.
• 이는 k의 값을 배열의 길이로 나눈 나머지만큼만 배열을 회전시키면 된다는 의미가 된다.

Input	k	Output
[1, 2, 3, 4, 5, 6, 7]	0	[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]	1	[7, 1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7]	2	[6, 7, 1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6, 7]	3	[5, 6, 7, 1, 2, 3, 4]
[1, 2, 3, 4, 5, 6, 7]	4	[4, 5, 6, 7, 1, 2, 3]
[1, 2, 3, 4, 5, 6, 7]	5	[3, 4, 5, 6, 7, 1, 2]
[1, 2, 3, 4, 5, 6, 7]	6	[2, 3, 4, 5, 6, 7, 1]
[1, 2, 3, 4, 5, 6, 7]	7	[1, 2, 3, 4, 5, 6, 7]

• 위의 특징을 고려하여 새로운 k를 위해 변수 newK를 선언한다.

  int newK = k % nums.length;
  

• 새로운 배열을 만들지 않고, 배열 속 요소의 위치를 변경할 때는 임시 공간에 배열의 요소를 저장하는 작업이 필요하다.
• 회전 시킬 요소를 임시 공간에 저장하도록 한다. 여기서는 임시 공간으로 자료구조 Stack를 선택했다.

  Stack<Integer> stack = new Stack<Integer>();
  for (int i = 0; i < newK; i++)
    stack.push(nums[nums.length - 1 - i]);
  

• 임시 공간에 들어가지 않은 요소들의 위치를 옮겨준다.

  for (int i = nums.length - 1 - newK; -1 < i; i--)
    nums[i + newK] = nums[i];
  

• 임시 공간 속 요소들을 회전 시킬 위치로 옮겨준다.

  for (int i = 0; i < newK; i++) 
    nums[i] = stack.pop();