[LeetCode] 189. Rotate Array

https://leetcode.com/problems/rotate-array

개요

1. 배열을 k번 오른쪽으로 회전해라

문제 해결 아이디어

• 배열길이=7, k=3 일때 인덱스 이동
  

1. k를 더하자
   [0번 ➡️ 3번
   1번 ➡️ 4번
   2번 ➡️ 5번
   3번 ➡️ 6번
   4번 ➡️ 7번
   5번 ➡️ 8번
   6번 ➡️ 9번]

2. 배열길이로 나머지 연산하자
   [0번 ➡️ 3번
   1번 ➡️ 4번
   2번 ➡️ 5번
   3번 ➡️ 6번
   4번 ➡️ 0번
   5번 ➡️ 1번
   6번 ➡️ 2번]

🧐 나머지 연산을 이용하자

➡️ 현재 인덱스가 이동해야할 인덱스를 (현재 인덱스 + K) % 배열 길이로 계산할 수 있다

의사 코드

1. 주어진 배열을 clone 한다.
2. clone 한 배열을 돈다.
3. clone 한 배열에서 원래 인덱스의 값을 참조한다.
4. 원래 인덱스에서 이동할 인덱스를 연산한다.
5. 주어진 배열에서 이동할 인덱스의 값을 참조한 값으로 변경한다.

복사한 배열 = 주어진 배열
for(인덱스 = 0 to 주어진 배열의 길이){
	원래값 = 복사한 배열[인덱스]
	이동할 인덱스 = (인덱스 + k) % 주어진 배열의 길이
    주어진 배열[이동할 인덱스] = 원래값
}

결과

전체 코드 github 링크

다른 풀이

public static void reverse(int[] nums,int start,int end){
        while(end>start){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
    public void rotate(int[] nums, int k) {
        k%= nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }

구간 내 절대적인 순서가 바뀌지 않는다는 점을 이용했다.
(k+1:nums.length-1) 과 (0:k) 두 구간으로 나눠 세번 뒤집었다.
나의 풀이는 추가 공간을 요구하는데, 이 풀이는 추가 배열 공간이 필요 없다.
또한 시간복잡도도 O(N)으로 동일하다.

ex>
(1)0 1 2 3 4 5 6
(2)6 5 4 3 2 1 0
(3)4 5 6 3 2 1 0
(4)4 5 6 0 1 2 3