풀어드렸음 분할정복 냄새 나라고 퀵소트 쓰고
퀵소트 썻으니 아마 big o 는 nlogn 이라 카더라
아참 과제로는 못쓰게 크기별로 다 넓이 재서 품
글쓰고보니 이스케이프문 못쓰네 다 날라가네 알아서 참고하셈
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void swap1(int *a, int *b)
{
(*a)^=(*b)^=(*a)^=(*b);
}
void QSort( int *nArr, int nStart, int nEnd)
{
int nPivot = nArr[ nStart ];
int nLeft = nStart + 1;
int nRight = nEnd;
// 개수가 적어서 찾을 것이 없는가?
if( nEnd - nStart <= 0 )
{
return;
}
while( 1 )
{
// Left를 찾는다.
for( ; nLeft <= nEnd ; nLeft++ )
{
if( nPivot < nArr[ nLeft ] )
{
break;
}
}
// Right를 찾는다.
for( ; nRight > nStart ; nRight-- )
{
if( nPivot > nArr[ nRight ] )
{
break;
}
}
// 바꿔야할 상황이라면 바꾼다.
if( nLeft <= nEnd && nRight > nStart && nLeft < nRight )
{
swap1( &nArr[ nLeft ], &nArr[ nRight ] );
continue;
}
// Left, Right가 모두 범위 밖으로 나갔다면 배열 안의 숫자는 모두 같은 숫자다.
if( nRight <= nStart && nLeft > nEnd )
{
return;
}
// 조건이 된다면 왼쪽 Array를 Recursive로 돌린다.
if( nRight > nStart )
{
// Pivot과 Right를 바꾼다.
swap1( &nArr[ nStart ], &nArr[ nRight ] );
QSort( nArr, nStart, nRight );
}
// 오른쪽 Array는 지금의 함수를 재사용.
nStart = nRight + 1;
nPivot = nArr[ nStart ];
nLeft = nStart + 1;
nRight = nEnd;
// 개수가 적어서 찾을 것이 없는가?
if( nEnd - nStart <= 0 )
{
return;
}
}
}
void findMax(int *arr ,int size)
{
int ch=0,midx=0,vol=0;
for(int i=0;i<size;i++)
{
if(arr[i] != midx)
{
midx = i;
if((arr[midx]*(size-i)) > vol)
{
vol = arr[midx]*(size-i);
ch = arr[midx];
}
}
}
printf(" vol = %d ",vol);
printf("ch = %d ",ch);
}
int main()
{
int n;
int *arr;
srand((unsigned int)time(NULL));
printf("How many data you want to make?");
scanf("%d", &n);
if( n <= 0 || n >= 50 )
return 0;
arr = (int *)malloc(sizeof(int)*n);
for(int i =0;i<n;i++)
arr[i] = rand()P + 1;
QSort(arr, 0, n-1);
for(int i =0;i<n;i++)
printf("%d",arr[i]);
findMax(arr,n);
while(1);
return 0;
}
댓글 0