배열을 효율적으로 회전시키는 대표적인 기법 중 하나인 반전(Reversal) 알고리즘은 추가 메모리 없이 배열을 원하는 만큼 회전할 수 있는 우아한 방법입니다. 세 번의 반전 연산만으로 회전을 완료할 수 있어 널리 사용됩니다. 아래는 이 알고리즘을 Java로 구현한 예제입니다.
예제 코드
import java.io.*;
public class Demo{
static void rotate_left(int my_arr[], int no_of_rotation){
int n = my_arr.length;
array_reversal(my_arr, 0, no_of_rotation - 1);
array_reversal(my_arr, no_of_rotation, n - 1);
array_reversal(my_arr, 0, n - 1);
}
static void array_reversal(int my_arr[], int start, int end){
int temp;
while (start < end) {
temp = my_arr[start];
my_arr[start] = my_arr[end];
my_arr[end] = temp;
start++;
end--;
}
}
public static void main(String[] args){
int my_arr[] = { 45, 67, 89, 91, 23, 0, 11 };
rotate_left(my_arr, 4);
System.out.println("The array after rotating is ");
for (int i = 0; i < my_arr.length; i++)
System.out.print(my_arr[i] + " ");
}
}실행 결과
The array after rotating is 23 0 11 45 67 89 91
코드 상세 설명
Demo 클래스에는 rotate_left라는 함수가 정의되어 있습니다. 이 함수는 회전할 배열과 회전 횟수를 매개변수로 전달받으며, 함수 내부에서는 먼저 배열의 길이를 변수 n에 저장합니다.
반전 알고리즘의 핵심은 다음과 같은 세 단계의 반전 연산입니다.
1단계: 첫 번째 요소부터 (회전 횟수 − 1)번째 요소까지의 앞부분을 반전합니다.
2단계: 회전 횟수번째 요소부터 마지막 요소까지의 뒷부분을 반전합니다.
3단계: 전체 배열을 한 번 더 반전하면 회전이 완성됩니다.
array_reversal 함수는 배열, 시작 인덱스, 끝 인덱스를 매개변수로 받습니다. 시작 인덱스가 끝 인덱스보다 작은 동안 temp 임시 변수를 사용해 양쪽 끝의 요소를 서로 교환하고, 시작 인덱스는 하나씩 증가시키며 끝 인덱스는 하나씩 감소시켜 두 포인터가 서로 만날 때까지 진행합니다.
main 함수에서는 정수 배열을 선언하고 초기화한 뒤, rotate_left 함수를 호출해 배열을 왼쪽으로 4칸 회전시키고 그 결과를 출력합니다.
알고리즘의 장점
이 방식의 가장 큰 장점은 효율성입니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 별도의 임시 배열 없이 제자리(in-place)에서 회전을 수행할 수 있습니다. 따라서 대용량 데이터를 다룰 때에도 메모리 부담 없이 안정적으로 활용할 수 있습니다.