문제

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

구현 전 예상 풀이

현재 인덱스 값을 k 이전 인덱스의 값으로 재귀적으로 변경한다.
방문한 인덱스는 기록한다.

구현 코드

class Solution {
    int[] nums;
    int k;
    boolean[] visit = new boolean[100000];

    public void rotate(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        IntStream.range(0, nums.length)
                .forEach(this::rec);
    }

    private int rec(int idx) {
        if (visit[idx]) {
            return nums[idx];
        }

        visit[idx] = true;

        int num = nums[idx];
        nums[idx] = rec(index(idx));
        return num;
    }

    private int index(int idx){
        int index = idx - k;

        while (index < 0) {
            index += nums.length;
        }

        return index;
    }
}

예전 풀이

class Solution {
    int[] nums = null;
    int k = 0;
    public void rotate(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        next(0);
    }
    
    private void next(int n){
        if(n >= nums.length)
            return;
        int num = nums[n];
        next(n + 1);
        nums[nextNum(n)] = num;
    }
    
    private int nextNum(int n){
        return (n + k) % nums.length;
    }
}

다른 사람 풀이

nums: 1 2 3 4 5 6 7
k: 3
reverse1: 7 6 5 4 3 2 1
reverse2: 5 6 7 4 3 2 1
reverse3: 5 6 7 1 2 3 4

• 7
  reverse1: index-0 이동 (+1)
  reverse2: index-2 이동 (+2)
• 6
  reverse1: index-1 (+3)
  reverse2: 움지이지 않음
• 5
  reverse1: index-2 이동 (+5)
  reverse2: index-0 이동 (-2)
• 4
  reverse1: 움직이지 않음
  reverse3: index-6 이동 (+3)
• 3
  reverse1: index-4 이동 (+2)
  reverse3: index-5 이동 (+1)
• 2
  reverse1: index-5 이동 (+4)
  reverse3: index-4 이동 (-1)
• 1
  reverse1: index-6 이동 (+6)
  reverse3: index-3 이동 (-3)

모든 숫자가 +3 만큼 이동하였다.

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);
}

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

189. Rotate Array
다른 사람 풀이 링크