배열 회전(Array Rotation)은 배열의 요소들을 지정된 횟수만큼 왼쪽 또는 오른쪽으로 이동시키는 작업입니다. 이 글에서는 최대공약수(GCD)를 활용하는 '저글링 알고리즘(Juggling Algorithm)'을 사용해 배열을 왼쪽으로 회전하는 Java 프로그램을 소개합니다.
아래는 배열 회전을 수행하는 Java 프로그램입니다.
예제 코드
public class Demo{
void rotate_left(int my_arr[], int d, int len){
d = d % len;
int i, j, k, temp;
int divisor = greatest_Common_divisor(d, len);
for (i = 0; i < divisor; i++){
temp = my_arr[i];
j = i;
while (true){
k = j + d;
if (k >= len)
k = k - len;
if (k == i)
break;
my_arr[j] = my_arr[k];
j = k;
}
my_arr[j] = temp;
}
}
void display_arr(int my_arr[], int size){
int i;
for (i = 0; i < size; i++)
System.out.print(my_arr[i] + " ");
}
int greatest_Common_divisor(int a, int b){
if (b == 0)
return a;
else
return greatest_Common_divisor(b, a % b);
}
public static void main(String[] args){
Demo my_inst = new Demo();
int my_arr[] = { 5, 7, 89, 91, 34, 21, 11, 0 };
System.out.println("Rotating the array to the left ");
my_inst.rotate_left(my_arr, 2, 8);
System.out.println("Displaying the array from a specific index ");
my_inst.display_arr(my_arr, 8);
}
}실행 결과
Rotating the array to the left Displaying the array from a specific index 89 91 34 21 11 0 5 7
코드 동작 원리
1. rotate_left 메서드
Demo라는 이름의 클래스에는 rotate_left 메서드가 정의되어 있습니다. 이 메서드는 세 개의 매개변수를 받습니다.
- my_arr: 회전할 대상 배열
- d: 배열을 회전시킬 칸 수
- len: 배열의 크기
먼저 d = d % len 연산을 통해 회전 횟수를 배열 크기보다 작게 정규화합니다. 예를 들어 배열 크기가 8인데 10칸 회전을 요청하면 실제로는 2칸만 회전하면 되기 때문입니다.
이후 d와 len 값을 인자로 전달하여 greatest_Common_divisor 함수를 호출하고, 그 결과값(최대공약수)만큼 for 루프를 반복하면서 각 사이클(cycle)의 요소들을 한 번에 이동시킵니다. 이 방식 덕분에 임시 변수 하나만 사용해도 전체 배열을 효율적으로 회전할 수 있으며, 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.
2. display_arr 메서드
display_arr 메서드는 배열의 모든 요소를 순서대로 화면에 출력하는 역할을 합니다. 반복문을 사용해 인덱스 0부터 마지막 요소까지 공백으로 구분하여 출력합니다.
3. greatest_Common_divisor 메서드
greatest_Common_divisor 메서드는 두 수의 최대공약수(GCD)를 구하는 재귀 함수입니다. 유클리드 호제법(Euclidean Algorithm)을 기반으로 하며, 두 번째 인자가 0이 될 때까지 자기 자신을 재귀적으로 호출하여 최대공약수를 반환합니다.
main 메서드의 실행 흐름
main 메서드에서는 먼저 Demo 클래스의 인스턴스를 생성합니다. 그다음 8개의 요소를 가진 배열 {5, 7, 89, 91, 34, 21, 11, 0}을 정의하고, rotate_left 메서드를 호출하여 배열을 왼쪽으로 2칸 회전시킵니다. 마지막으로 display_arr 메서드를 통해 회전된 배열의 결과를 출력합니다.
실행 결과를 보면 원래 배열의 앞부분에 있던 5, 7이 맨 뒤로 이동하고, 나머지 요소들이 앞으로 당겨져 89 91 34 21 11 0 5 7 순서로 출력된 것을 확인할 수 있습니다.