[LeetCode] 189. Rotate Array - 문제풀이

Description

주어진 K만큼 배열의 요소를 오른쪽으로 shift하는 문제입니다.

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 <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Solution 1. 추가 Array 공간 활용

public void rotate(int[] nums, int k) {
		// 1. Using Extra Array
    int[] nums2 = Arrays.copyOf(nums,len);
    for (int i = 0; i < len; i++) {
        if(i<k){ // 로테이션 ( 전체 길이 - 로테이션 횟수 + i )
            nums[i] = nums2[len-k+i];
        }else{ // 나머지 뒤로 (현재 인덱스 - 로테이션 횟수)
            nums[i] = nums2[i-k];
        }
    }
}

추가 배열(nums2)를 사용하여 원본배열을 복사해 두고 원본 배열에 rotate된 값들을 순차적으로 담아내는 코드입니다.

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(N)

Solution 2. Reverse 활용

public void rotate(int[] nums, int k) {

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

    //2. reverse 이용
    reverse(nums,0,len-1); //step1 전체 reverse    [7,6,5,4,3,2,1]
    reverse(nums,0,k-1);   //step2 로테이션 숫자들 reverse [ 5,6,7,4,3,2,1 ]
    reverse(nums,k,len-1); //step3 나머지 숫자들 reverse [ 5,6,7,1,2,3,4 ]

}

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

요소를 반전시키는 Reverse 메서드를 활용하는 방법입니다. 먼저 전체 요소를 반전시키고 로테이트 시켜야하는 0~k-1 영역만큼 반전 후 나머지 영역도 반전시켜 주면 로테이트된 값과 동일한 결과를 얻을 수 있습니다.

Reference

Rotate Array - LeetCode