Baekjoon] 소트인사이드 (퀵정렬)

단순하게 배열을 정렬하는 문제다.

퀵소트를 이용해서 풀었는데 정말 삽질을 많이했다.

https://www.acmicpc.net/problem/1427

문제를 보면 알겠지만 10억이하의 수를 받고 내림차순 정렬하는 문제다.

풀면서 느낀점.

 1. 문제를 잘보자!

입력N이 1,000,000,000이라는 어마무지한 조건이 있었다. 어떻게 10억을 받지..하면서 

스텍사이즈가 초과하길래 10억 그리고 1짜리 동적 배열을 할당했다. 물론 이렇게 해도 풀리긴 하지만..사실 10억은 함정이었고 단순히 10자리 char배열만 받으면 되는거였다. 하.........단순해 char arr[11]만 해줘도 되는걸.. 하... 문제를 잘 보자

2. 예외처리를 잘 하자!

첫 번째로 고려를 못한 사항은(이게 좀 크리티컬했다) l포인터와 r포인터가 MAX값을 안줘서 탈출해버리는 문제였다. 이건 값을 줘서 해결.

두 번째로 고려를 못한 사항은 154811223 과 같이 동일한 숫자가 나올 수 있는것을 생각하지 못했다.

이 문제는 l포인터의 값을 증가시킬 때 pivot>=arr[left+1]값을 조건에 넣어서 해결했다. 원래 코드에서는 '='을 넣지않아서 같은수가 바로 뒤나 다른곳에서 또 나오면 처리를 못하는 문제가 있었다.

처참한 흔적..

처참한 흔적...하..

그렇다.. 난 보인가봉가....ㅋ....

답을 돌렸는데 segmentation err가 뜨는 것 아닌가. 첫 번재 문제때문이었다. 하하... 

내가 작성한 코드는 아래와 같고.. 알고리즘 허접이라 퀵소트를 틀에 맞게(틀이라고 해야하나?) 짰는지는 보장하지 못하나 첨부는 한다.하하하하 이러면서 느는거지뭐..

내가 사용한 퀵소트의 알고리즘은 다음과 같다.

Log를 보고싶으면 전역변수에서 MOD를 DEBUG로 바꾸면 된다능...하하..

#include
#include
//#include

#define DEBUG 1
#define EXE 0
int MOD = EXE;

void sort(char arr[15],int l, int r) {
	int MAX_ARR_SIZE = r;
	int MIN_ARR_SIZE = l;
	char p=arr[l];
	int left = l;
	int right = r;



	if(l>=r) {
		if(MOD) printf("r이 l보다 작아져서r return [l r]=[%d %d];\n",l,r);
		return;
	}

	if((r-l)==1) {
		int min = arr[l]arr[r]?arr[l]:arr[r];

		arr[l]=min;
		arr[r]=max;
		if(MOD) printf("원소가 두개남아서 return [l r]=[%d %d];\n",l,r);
		if(MOD) printf("%s\n",arr);
		return;
	}	


	while(1) {
		char temp;
		while( (p>=arr[left+1])  &&  ((left+1)<=MAX_ARR_SIZE) ) {
			left++;
			if(MOD) printf("Left ptr 이동 현재값은 [left,val][pivot] = [%d %c] %c\n",left,arr[left],p);
		}
		while( (p=MIN_ARR_SIZE) ) {
			right--;
			if(MOD) printf("right ptr 이동 현재값은 [right,val][pivot] =  = [%d %c] %c\n",right,arr[right],p);
		}
		if(left==right) {
			if(MOD) printf("Left 와 Right 만나거나 넘어서 break; \n");
			temp=arr[l];
			arr[l]=arr[left];
			arr[left]=temp;
			break;
		}
		if(MOD) printf("Left+1과 right 교환 [%c->%c] break; \n",arr[left+1],arr[right]);
		temp=arr[left+1];
		arr[left+1]=arr[right];
		arr[right]=temp;
		if(MOD) printf("%s\n",arr);
	}
	if(MOD) printf("%s\n",arr);


	sort(arr,l,left-1);
	sort(arr,left+1,r);

}

void invertPrt(char* arr) {
	int length= strlen(arr);
	int i=0;
	for(i=length-1;i>=0;i--) {
		printf("%c",arr[i]);
	}
	printf("\n");
}

int main() {

	//char* arr=(char*)malloc(sizeof(char)*1000000001);
	char arr[15];

	scanf("%s",arr);

	if(MOD) printf("strlen = %d\n",strlen(arr));

	sort(arr,0,strlen(arr)-1);
	invertPrt(arr);
	//printf("%s\n",arr);



	//free(arr);

	return 0;
}