[알고리즘] 0.3 배열 회전

배열 arr[]과 위치 s(Start Point), t(Turning Point)가 있을 때,

오른쪽으로 한 칸씩 이동하고, arr[t]는 arr[s]로 복사하는 것을 1만큼 오른쪽으로 회전시켰다고 가정한다.

 

0. 배열 회전

[ 코드 ]

#include <iostream>

using namespace std;

void right_rotate(int arr[], int s, int t){
	int i, last;
	last = arr[t]; // 끝지점의 배열을 호출한다.
	// s : Start 지점
	// t : End 지점

	for ( i = t; i > s; i--){
		arr[i] = arr[i-1];
		// 한칸씩 오른쪽을 밀려가며 변수를 호출 받는다.
		// End 지점을 호출 받았으므로, End 지점이 비었다.
		// End 지점에 End-1의 변수메모리를 넣는다.
		// End-1 지점에 End-2의 변수메모리를 넣는다.
		// 오른쪽에서부터, 오른쪽으로 한칸씩 밀어가며 변수를 호출한다.
	}
	arr[s] = last;
	// 반복문이 끝난 시점에서 Start지점은 Start+1의 주소로 이동하였으므로 비었다.
	// 즉, Start 지점에 다시 End 지점의 메모리를 할당하여서 최종적으로 배열 회전을 종료한다.
}

int main(void){
	int arr[] = {1,4,5,6,7,7,9};
	cout << "변경 전 배열" << endl;
	int len = sizeof(arr) / sizeof(arr[0]);
	for (int i =0 ; i< len ; i++){
		cout << arr[i];
	}
	cout << ""<< endl;
	right_rotate(arr, 3,len-1);
	cout << "변경 후 배열" << endl;
	for (int i=0; i < len; i++){
		cout << arr[i];
	}
	cout << "" << endl;
	return 0;
}

[ 결과 ]

tot4766@tot4766:~/main/코딩/c++/알고리즘$ ./a.out
변경 전 배열
1456779
변경 후 배열
1459677