알고스팟/튜토리얼
[소스코드/C++] LECTURE
Makeii
2016. 2. 29. 00:44
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | /*입력받은 문자열을 2개씩 분리한 뒤 정렬하여 합친 결과를 반환하여라.*/ #include <iostream> #include <string> using namespace std; #define MAX_SIZE 1000 //문자열의 최대사이즈는 1000 //void quickSort(string *arr, int left, int right, int size); void sort(string *arr, int size); int main(){ int count; //테스트케이스 수 int index = 0; //while문을 돌릴 변수 int size = 0; //문자열의 절반 길이를 넣는 변수(2개씩 묶이니까) string str; string result; //정렬이 완료된 문자열을 넣는 변수 string *super; //테스트케이스 개수만큼 나열될 문자 배열 string *arr; //자른 문자열을 저장할 변수 cin>>count; super = new string[count]; for(int i=0;i<count;i++){ cin>>str; size = (str.length())/2; arr = new string[MAX_SIZE]; while(!str.empty()){ //2개씩 자르기 arr[index] = str.substr(0, 2); //cout<<arr[index]<<" / "<<str<<endl; str.erase(0,2); index++; } //quickSort(arr, 0, size-1, size); sort(arr, size-1); for(int j=0;j<size;j++){ result.append(arr[j]); } super[i] = result; //합쳐진 문자열을 super에 대입 //기존에 쓰이던 변수들 초기화 index = 0; result.erase(); } for(int i=0;i<count;i++){ cout<<super[i]<<endl; } delete []super; delete []arr; return 0; } /*void quickSort(string *arr, int left, int right, int size){ if(left<right){ int i = left; int j = right+1; string pivot = arr[left]; do{ do { i++; cout<<"i : "<<i<<" "; if(i>j) break; }while((pivot.compare(arr[i])>=0)&&i<=right); cout<<endl; do { j--; cout<<"j : "<<j<<" "; if(j<i) break; }while((pivot.compare(arr[j])<0)&&j>=left); cout<<endl; if(i<j){arr[i].swap(arr[j]);} }while(i<j); arr[left].swap(arr[j]); cout<<"swap : "<<left<<"<->"<<j<<endl; for(int i=0;i<size;i++){ cout<<arr[i]<<" "; } cout<<endl; cout<<"j-1 "<<j-1<<" j+1 "<<j+1<<endl; quickSort(arr, left, j-1, size); quickSort(arr, j+1, right, size); } }*/ void sort(string *arr, int size){ int *stack = new int[2*size+2]; int top = -1; int start, end, left, right; string pivot; //stack push stack[++top] = size; stack[++top] = 0; while(top!=-1){ //stack이 비어있지 않을 때 //stack pop(먼저 들어간게 나중에) start = stack[top--]; //cout<<"start : "<<start<<endl; //cout<<"start top : "<<top<<endl; end = stack[top--]; //cout<<"end : "<<end<<endl; //cout<<"end top : "<<top<<endl; if(start<end){ //정렬할만한 크기가 될 때 left = start; right = end+1; pivot = arr[left]; do { do {left++;} while((left<=end)&&(pivot.compare(arr[left])>=0)); //pivot보다 크면 멈춤 do {right--;} while((right>=start)&&(pivot.compare(arr[right])<0)); //pivot보다 작으면 멈춤 if(left<right){ //교차하지 않았을 때 arr[left].swap(arr[right]); } }while(left<right); arr[start].swap(arr[right]); /*for(int i=0;i<size+1;i++){ cout<<arr[i]<<" "; } cout<<endl;*/ //앞으로 정렬해야 할 범위들을 stack에 저장 stack[++top] = end; stack[++top] = right+1; stack[++top] = right-1; stack[++top] = start; } } delete []stack; } | cs |
quickSort함수는 재귀/sort함수는 스택배열을 활용한 비재귀 - 둘 다 퀵정렬
RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow)
런타임 오류 발생했었음
이유는 문자열을 받는 arr배열의 사이즈가 모자랐기 때문
문제에 최대사이즈가 1000이라고 나와있는데 배열의 크기를 30으로 잡았었음