<C언어 알고리즘> 정렬 후 회전된 배열

“정렬 후 회전된 배열”이란 (5, 8, 9, 2, 3, 4)와 같은 배열을 말한다. 즉, 정렬이 된 후에 회전 연산이 0회 이상 적용된 배열이다. 회전 연산이란 배열의 마지막 원소가 처음으로 이동하고 나머지 원소들이 오른쪽으로 한 칸씩 이동하는 것을 말한다. 예를 들어, (2, 3, 4, 5, 8, 9)는 정렬된 배열이고 여기에 회전 연산을 1회 적용하면 (9, 2, 3, 4, 5, 8)이 되고 여기에 회전 연산을 추가로 2회 적용하면 (5, 8, 9, 2, 3, 4)가 된다. 따라서 (5, 8, 9, 2, 3, 4)는 정렬 후 회전된 배열이다.

(a) 길이가 n 인 정렬후 회전된 배열 A[0..n-1]가 주어질 때, 이 배열 A 에서 최댓값을 찾는 알고리즘을 설계하시오.

(b) 정렬후 회전된 배열 A[0..n-1]가 회전연산을 몇번 적용한 것인지 알아내는 알고리즘을 설계하시오.

(c) 정렬후 회전된 배열 A[0..n-1]와 k 가 주어질 때, A 안에서 k 를 탐색하는 알고리즘을 설계하시오. 즉, A 의 원소 중에 k 가 있으면 그 위치(index)를 출력하고 없으면 -1 을 출력합니다.

---

Solution

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int find_max(int *arr,int size)			//(a)
{
	for(int i=1;i<size;i++)
		if(arr[i-1]>arr[i])
			return arr[i-1];
	return arr[size-1];
}

int rotated_count(int *arr,int size)	//(b)
{
	for(int i=1;i<size;i++)
		if(arr[i-1]>arr[i])
			return i;
	return 0;
}

int find_k(int *arr,int k,int size)		//(c)
{
	for(int i=0;i<size;i++)
		if(arr[i]==k)
			return i;
	return -1;
}

int main(void)
{
	int size, *arr=NULL, k,random;
	srand((unsigned)time(NULL));

	printf("size: ");
	scanf("%d", &size);
	arr=(int *)malloc(size*sizeof(int));

	printf("initial array: ");
	for(int i=0;i<size;i++)
	{
		arr[i]=rand()%100;
		printf("%d ", arr[i]);
	}
	printf("\n");

	for(int i=0;i<size-1;i++)			//sort array
		for(int j=i+1;j<size;j++)
			if(arr[i]>arr[j])
			{
				int temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
	printf("sorted array: ");
	for(int i=0;i<size;i++)
		printf("%d ", arr[i]);
	printf("\n");

	random=rand()%size;				//rotate array
	printf("random:%d\n", random);
	for(int i=0;i<random;i++)
	{
		int temp=arr[size-1];
		for(int j=size-1;j>=0;j--)
			arr[j]=arr[j-1];
		arr[0]=temp;
	}
	printf("rotated array: ");
	for(int i=0;i<size;i++)
		printf("%d ", arr[i]);
	printf("\n");

	printf("max:%d,rotated count:%d\n",find_max(arr,size),rotated_count(arr,size));
	printf("k: ");
	scanf("%d", &k);
	printf("%d\n",find_k(arr,k,size));

	free(arr);
	return 0;
}