//https://algospot.com/judge/problem/read/SORTGAME#include <iostream>usingnamespacestd;intC;intN;intdata[8+1];intsortData[8+1];voidReverse(intnums[],intfirst,intend){inttemp=0;intend_index=end;inthalf=(first+end)/2;for(inti=first;i<=half;i++){temp=nums[i];nums[i]=nums[end_index];nums[end_index]=temp;end_index--;}}voidq_sort(intnums[],intleft,intright){intpivot,l_hold,r_hold;l_hold=left;r_hold=right;pivot=nums[left];if(left==right){return;}while(left<right){while((pivot<=nums[right])&&(left<right)){right--;}if(left!=right){nums[left]=nums[right];left++;}while((pivot>=nums[left])&&(left<right)){left++;}if(left!=right){nums[right]=nums[left];right--;}}nums[left]=pivot;pivot=left;left=l_hold;right=r_hold;if(left<pivot){q_sort(nums,left,pivot-1);}if(right>pivot){q_sort(nums,pivot+1,right);}}voidQuickSort(intnums[],intsize){q_sort(nums,0,size-1);}intmain(){intnoSortStartIndex=-1;intnoSortEndIndex=-1;intmin=999999;intminIndex=0;boolisSame=false;intcount=0;cin>>C;while(C--){for(inti=0;i<8;i++){data[i]=0;sortData[i]=0;}cin>>N;for(inti=0;i<N;i++){cin>>data[i];sortData[i]=data[i];}QuickSort(sortData,N);while(!isSame){for(inti=0;i<N;i++){if(data[i]!=sortData[i]){break;}if(i==N-1){isSame=true;}}if(isSame)break;for(inti=0;i<N;i++){if(data[i]!=sortData[i]){if(noSortStartIndex==-1){noSortStartIndex=i;}else{noSortEndIndex=i;}}}for(inti=noSortStartIndex;i<=noSortEndIndex;i++){if(min>data[i]){min=data[i];minIndex=i;}}Reverse(data,noSortStartIndex,minIndex);count++;noSortStartIndex=-1;noSortEndIndex=-1;min=999999;minIndex=0;}// end of while(!isSame)cout<<count<<endl;count=0;isSame=false;}return0;}
firenin
사용한 방법은 입력받은 수열과 정렬한 수열이 다를 경우
진행합니다.
진행 방식은 정렬이 안된 구역의 첫 인덱스(noSortStartIndex)와,
그 구역 내 가장 작은 수의 인덱스(minIndex) 를
Reverse 를 하고, 카운트를 올리며 이것을 반복하는 방식입니다.
*ex)
Reverse(data, noSortStartIndex, minIndex);
1. 3 4 1 2
noSortStartIndex : 0
minIndex : 2
2. 1 4 3 2
noSortStartIndex : 1
minIndex : 3
3. 1 2 3 4 정렬된 배열과 같으므로 종료
주어진 테스트 케이스로는 원하는 결과가 나오는데
어떤 부분에서 틀린지 잘 모르겠습니다.
도와주세요.
9년 전