[acmicpc] 10814 나이순 정렬 정답 코드

#include <stdio.h> 
#include <stdlib.h>
 
typedef struct _Point
{
    int m_nAge;
    char* m_lpszName;
    int m_nIndex;
    bool operator>(struct _Point& other) const;
} Point;
 
typedef Point *Points;
 
bool _Point::operator>(_Point& other) const
{
    if (this->m_nAge > other.m_nAge)
    {
        return true;
    }
    else if (this->m_nAge == other.m_nAge)
    {
        if (this->m_nIndex > other.m_nIndex)
        {
            return true;
        }
    }
    return false;
}
 
void merge(Points* arr, int start1, int end1, int start2, int end2)
{
    // 앞 배열의 인덱스와 뒤 배열의 인덱스 
    int i = start1, j = start2;
 
    // 임시 배열 (정렬을 위한)
    int nArrSize = end2 - start1 + 1;
    int index = 0;
    Points pTemp = (Points)malloc(sizeof(Point) * nArrSize);
 
    // 두 배열을 오름차순으로 pTemp에 저장 
    while (i <= end1 || j <= end2)
    {
        // 배열 index out of bound 오류 방지
        if (i > end1)
        {
            (pTemp + index)->m_nAge = (*arr + j)->m_nAge;
            (pTemp + index)->m_lpszName = (*arr + j)->m_lpszName;
            (pTemp + index)->m_nIndex = (*arr + j)->m_nIndex;
            index++; j++;
        }
        else if (j > end2)
        {
            (pTemp + index)->m_nAge = (*arr + i)->m_nAge;
            (pTemp + index)->m_lpszName = (*arr + i)->m_lpszName;
            (pTemp + index)->m_nIndex = (*arr + i)->m_nIndex;
            index++; i++;
        }
        else if ((*(*arr + i)) > (*(*arr + j)))
        {
            (pTemp + index)->m_nAge = (*arr + j)->m_nAge;
            (pTemp + index)->m_lpszName = (*arr + j)->m_lpszName;
            (pTemp + index)->m_nIndex = (*arr + j)->m_nIndex;
            index++; j++;
        }
        else
        {
            (pTemp + index)->m_nAge = (*arr + i)->m_nAge;
            (pTemp + index)->m_lpszName = (*arr + i)->m_lpszName;
            (pTemp + index)->m_nIndex = (*arr + i)->m_nIndex;
            index++; i++;
        }
    }
 
    // pTemp 배열을 본래 arr 배열에 복사
    for (int i = 0; i < nArrSize; i++)
    {
        (*arr + start1 + i)->m_nAge = (pTemp + i)->m_nAge;
        (*arr + start1 + i)->m_lpszName = (pTemp + i)->m_lpszName;
        (*arr + start1 + i)->m_nIndex = (pTemp + i)->m_nIndex;
    }
 
    free(pTemp);
}
 
void mergeSort(Points* arr, int start, int end)
{
    // 종료 조건 
    if (start >= end) return;
 
    int nMid = (start + end) / 2;
 
    // 정렬이 된 배열 = 정렬이 된 배열의 절반 2개를 정렬하면서 합친 것이다. 
    mergeSort(arr, start, nMid);
    mergeSort(arr, nMid + 1, end);
    merge(arr, start, nMid, nMid + 1, end);
}
 
int main(void)
{
    unsigned int nInput;
    scanf("%u", &nInput);
 
    Points points = (Points)malloc(sizeof(Point) * nInput);
 
    char **lpszName = (char**)malloc(sizeof(char*) * nInput);
    for (int i = 0; i < nInput; i++)
    {
        *(lpszName + i) = (char*)malloc(sizeof(char) * 101);
    }
 
    for (unsigned int i = 0; i < nInput; i++)
    {
        scanf(" %d %s", &((points + i)->m_nAge), *(lpszName + i));
        (points + i)->m_lpszName = *(lpszName + i);
        (points + i)->m_nIndex = i;
    }
 
    mergeSort(&points, 0, nInput - 1);
 
    for (unsigned int i = 0; i < nInput; i++)
    {
        printf("%d %s\n", (points + i)->m_nAge, (points + i)->m_lpszName);
    }
 
    free(points);
 
    for (int i = 0; i < nInput; i++)
    {
        free(*(lpszName + i));
    }
    free(lpszName);
 
    return 0;
}
 

 

상당히 길게 짯습니다..