[JAVA]원하는 만큼 배열 숫자 당기는 알고리즘

아래 출처를 확인하면 다양한 방법으로 풀이가 되있으나 아래 방법이 시간복잡도에서 가장 빠른것이여서 정리해 둔다. 

public class RotateArray {

	void leftRotate(int arr[],int d, int n){
			//d가 n보다 클경우를 헨들링하기위한 처리
            //n이 클경우 d를 반환하게 된다.
			d = d%n; 
		
			int i,j,k,temp;
			int g_c_d = gcd(d,n);
			for(i=0;i<g_c_d; i++){
				temp = arr[i];
				j = i; 
				while(true){
					k = j+d;
					if(k>=n) k=k-n;
					if(k==i) break;
					arr[j]=arr[k];
					j=k;
				}
				arr[j]=temp;
			}
	}
	//최대공약수
	int gcd(int a,int b){
		if(b == 0){
			return a;
		}else{
			return gcd(b,a%b);
		}
	}
	////왼쪽의 숫자를 하나씩 앞으로 당기는 함수
	void leftRotatebyOne(int arr[], int n){
		int i, temp;
		temp= arr[0];   // 배열의 첫번째 숫자를 담는 변수
		
		for(i =0;i<n-1;i++){
			//뒤에있는 숫자를 앞배열에 담아준다.
			arr[i]=arr[i+1];
			//배열의 맨 마직막에 배열의 첫번째있던 숫자를 담아준다. 
			arr[n-1]=temp;
		}
	}
	//배열출력 함수
	void printArray(int arr[], int size){
		int i;
		for(i=0; i<size;i++){
			System.out.println(arr[i]+" ");
		}
	}
	
}

 public static void main(String[] args){
		RotateArray rotate = new RotateArray();
		
		int arr[]={1,2,3,4,5,6,7};
		int n = arr.length;
		rotate.leftRotate(arr, 3, n);
		rotate.printArray(arr, n);
}

Time complexity : O(n) 
Auxiliary Space : O(1)

 

[출처]https://www.geeksforgeeks.org/array-rotation/