[소스코드/C++] LECTURE

/*입력받은 문자열을 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;
}

quickSort함수는 재귀/sort함수는 스택배열을 활용한 비재귀 - 둘 다 퀵정렬

RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow)

런타임 오류 발생했었음

이유는 문자열을 받는 arr배열의 사이즈가 모자랐기 때문

문제에 최대사이즈가 1000이라고 나와있는데 배열의 크기를 30으로 잡았었음