[LeetCode/Java] 189. Rotate Array

0. 문제

https://leetcode.com/problems/rotate-array/?envType=study-plan-v2&envId=top-interview-150

1. 문제 설명

• 정수 배열 nums가 주어질 때 배열을 오른쪽으로 k만큼 회전시켜라.

2. 문제 풀이

2.1. 접근법

• 배열 nums와 똑같은 배열 tmp를 만든다.
• nums의 원소 개수만큼 반복문을 돌면서 (현재 인덱스 + k) % 전체 길이 위치에 현재 인덱스의 값을 넣는다.

3. 코드

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

4. 결과

5. 개선점

5.1. 시간 복잡도 개선

• 다음 풀이를 참고했다. (참고)
• 먼저 전체 원소를 반전시킨다.
• 그 다음 0부터 k-1 숫자들을 반전시키고, 나머지 원소들을 반전시킨다.
• 풀이

class Solution {
    public void rotate(int[] nums, int k) {
        int size = nums.length;
        k = k % lsize;

        reverse(nums,0,size-1); 
        reverse(nums,0,k-1);   
        reverse(nums,k,size-1);

    }

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

• 결과