알고리즘/acmicpc 코드
[acmicpc] 10814 나이순 정렬 정답 코드
ahdelron
2020. 4. 13. 00:17
|
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#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;
}
|
cs |
상당히 길게 짯습니다..