설명

• 배열에 저장된 값들을 회전시키는 알고리즘을 기본적으로 구현해보면, 한번 돌릴때마다 n번의 움직임이 필요하다.
• 즉, 8번 돌리면 8n번, 9번 돌리면 9n번.
  • 시간복잡도 O(m,n)
• 하지만 juggling 알고리즘 사용하면 O(n)이면 된다.
  • m번 회전시키고싶으면 그만큼 한번에 점프해버림.

코드

import java.io.IOException;
import java.util.Arrays;

/**
 * @Author: kbs
 */
public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();

        jugglingLeft(new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 3);
        jugglingRight(new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 3);
        System.out.println(sb);
    }

    private static void jugglingLeft(int[] arr, int countOfMove) {
        int n = arr.length;
        countOfMove %= n;
        int sizeOfSet = gcd(n, countOfMove);

        for (int indexOfElement = 0; indexOfElement < sizeOfSet; indexOfElement++) {
            int currentIndex = indexOfElement;
            int temp = arr[currentIndex];

            while (true) {
                int nextIndex = (currentIndex + countOfMove) % n;
                if (nextIndex == indexOfElement) break;
                arr[currentIndex] = arr[nextIndex];
                currentIndex = nextIndex;
            }

            arr[currentIndex] = temp;
        }

        System.out.println(Arrays.toString(arr));
    }

    private static void jugglingRight(int[] arr, int countOfMove) {
        int n = arr.length;
        countOfMove %= n;
        int sizeOfSet = gcd(n, countOfMove);

        for (int indexOfElement = 0; indexOfElement < sizeOfSet; indexOfElement++) {
            int temp = arr[indexOfElement];
            int currentIndex = indexOfElement;
            while (true) {
                int nextIndex = (currentIndex - countOfMove);
                if (nextIndex < 0) nextIndex = n + nextIndex;
                if (nextIndex == indexOfElement) break;

                arr[currentIndex] = arr[nextIndex];
                currentIndex = nextIndex;
            }
            arr[currentIndex] = temp;
        }

        System.out.println(Arrays.toString(arr));
    }

    private static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}