알고리즘/acmicpc 코드
[acmicpc] 11650 좌표 정렬하기 정답 코드
ahdelron
2020. 4. 12. 23:34
|
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
|
#include <stdio.h>
#include <stdlib.h>
typedef struct _Point
{
int m_X;
int m_Y;
bool operator>(struct _Point& other) const;
} Point;
typedef Point *Points;
bool _Point::operator>(_Point& other) const
{
if (this->m_X > other.m_X)
{
return true;
}
else if (this->m_X == other.m_X)
{
if (this->m_Y > other.m_Y)
{
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_X = (*arr + j)->m_X;
(pTemp + index)->m_Y = (*arr + j)->m_Y;
index++; j++;
}
else if (j > end2)
{
(pTemp + index)->m_X = (*arr + i)->m_X;
(pTemp + index)->m_Y = (*arr + i)->m_Y;
index++; i++;
}
else if ((*(*arr + i)) > (*(*arr + j)))
{
(pTemp + index)->m_X = (*arr + j)->m_X;
(pTemp + index)->m_Y = (*arr + j)->m_Y;
index++; j++;
}
else
{
(pTemp + index)->m_X = (*arr + i)->m_X;
(pTemp + index)->m_Y = (*arr + i)->m_Y;
index++; i++;
}
}
// pTemp 배열을 본래 arr 배열에 복사
for (int i = 0; i < nArrSize; i++)
{
(*arr + start1 + i)->m_X = (pTemp + i)->m_X;
(*arr + start1 + i)->m_Y = (pTemp + i)->m_Y;
}
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);
for (unsigned int i = 0; i < nInput; i++)
{
scanf(" %d %d", &((points + i)->m_X), &((points + i)->m_Y));
}
mergeSort(&points, 0, nInput - 1);
for (unsigned int i = 0; i < nInput; i++)
{
printf("%d %d\n", (points + i)->m_X, (points + i)->m_Y);
}
free(points);
return 0;
}
|
cs |
상당히 길게 짯습니다..