LeetCode(189)::Rotate Array

문제

Rotate Array - LeetCode

문제파악

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

배열의 값이  k스텝 마다 한칸씩 오른쪽으로 넘기면 될 거 같습니다.

문제풀이

해당 문제는 여러가지 풀이 기준이 존재하는데 인덱스 기준으로 생각할 수도 있으며, 시프트 방식으로 in-place로 문제를 해결할 수도 있다.

해결책  1 (인덱스 기준)

우선 index 기준으로 생각하면 된다.

k번 오른쪽으로 이동함을 고려하면 i번째 인덱스의 값이 (i+k)%n 인덱스에  위치함을 알수 있다.

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

해결책 2 (in-place )

class Solution {
   private static void swap(int[] arr, int idx1, int idx2) {
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
  }

   private static void reverse(int[] arr, int start, int end) {
    while(start < end) {
      swap(arr, start, end);
      start++;
      end--;
    }
   }

   private static void rightShift(int[] arr, int n) {
    int size = arr.length;
    reverse(arr, 0, n);
    reverse(arr, n+1, size-1);
    reverse(arr, 0, size-1);
   }
    
    public void rotate(int[] nums, int k) {
        rightShift(nums, nums.length-(k%nums.length)-1);
        
    }
}