[UVA] 11462

 

 

UVA 11462번 문제 입니다.

 

문제를 보면 n의 값이 0 < n <= 2000000 인 것을 확인 하실 수 있습니다. 그래서 처음엔 main문 안에다가 배열을 200만개 를 생성 해 주었지만 지역변수로는 배열이 200만개가 생성이 되지 않는 다는것을 확인했습니다. 그래서 찾아 본 결과 전역 변수로는 생성이 가능하다고 하여 전역변수로 배열을 200만개를 생성하니 정상적으로 생성 된 것을 확인 하였고 전부 0으로 초기화 해주었습니다. 그다음 정렬 알고리즘을 찾아보다가 제가 주로 사용 했었던 버블 정렬을 사용했지만 버블 정렬로 배열 200만개를 일일히 검색 하기에는 너무 시간이 오래걸려 Time Limit가 뜨게 됩니다. 그래서 가장 빠른 알고리즘을 찾아 보게 되었고 저는 퀵 정렬을 사용 했습니다. 다른 분들이 찾은 답을 보니 merge sort로 푸신 분도 계시더군요..ㅎㅎ 선택 알고리즘이나 삽입 알고리즘도 마찬가지로 Time limit가 뜨는 것을 확인 하였습니다.

 

while문으로 계속해서 n값을 입력받고 예외처리로 EOF처리와 0을 입력 할시 프로그램이 종료 되게 만들었습니다.

 

밑의 소스가 Accept 뜬 소스입니다 ^^ 밑의 소스로 문제를 푸니 Run Time 속도가 0.624초가 뜨네요.. ㄷㄷ

 

 

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

#define SWAP(a,b) {\
 int t;\
 t=a;\
 a=b;\
 b=t;\
}\

int i;
int p[2000000]={0,};

void QuickSort(int *arr, int length)
{
 int left,right;
 int key=0;

 if (length <= 1)
  return;

 key=arr[length-1];

 for (left=0,right=length-2;;left++,right--)
 {
  while (arr[left] < key)
  {
   left++;
  }
  while (arr[right] > key)
  {
   right--;
  }
  if (left >= right) break;            // 좌우가 만나면 끝
  SWAP(arr[left],arr[right]);
 }

 SWAP(arr[left],arr[length-1]);                   // 기준값과 i위치의 값 교환
 QuickSort(arr,left);                           // 왼쪽 구간 정렬
 QuickSort(arr+left+1,length-left-1);        // 오른쪽 구간 정렬
}

 

int main()
{

 int length=0;

 while(scanf("%d",&length)!=EOF && length !=0)
 {
  for(i=0;i<length;i++)
  {
   scanf("%d",&p[i]);
  }

  QuickSort(p,length);

  for(i=0;i<length-1;i++)
  {
   printf("%d ",p[i]);
  }
  printf("%d\n",p[i]);
 }

 return 0;
}