문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

1. 기본 아이디어 및 소스코드

• 제한시간 2초이다. C++인 경우 시간복잡도가 $O(N)$ 이라고 할 때, $N$이 1억이 되어야 1초가 걸린다고 들었다.

• 따라서, 최소한 시간복잡도가 선형 이하인 정렬 알고리즘을 골라서 사용해야한다.

• 그것을 만족하는 정렬 알고리즘은 Merge Sort이다.

• Merge Sort는 시간복잡도가 항상 $O(nlogn)$ 을 내는 알고리즘으로 Heap Sort와 같고, 최악상황의 Quick Sort($O(N^2)$)보다 안정적이다.

• Merge Sort는 분할 정복(Divide and Conquer) 방법을 사용한다. 이 방법은 대개 재귀 호출을 많이 사용한다. 과정은 다음과 같다.

  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 Merge Sort를 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

#include <iostream> #include <algorithm> using namespace std; void areaMerge(int numbers[], int left, int mid, int right) { int fIdx = left; int rIdx = mid + 1; int *sortArr = (int *)malloc(sizeof(int) * (right + 1)); int sIdx = left; while (fIdx <= mid && rIdx <= right) { if (numbers[fIdx] < numbers[rIdx]) { sortArr[sIdx] = numbers[fIdx++]; sIdx++; } else { sortArr[sIdx] = numbers[rIdx++]; sIdx++; } } if (fIdx > mid) { for (int i = rIdx; i <= right; i++) { sortArr[sIdx++] = numbers[i]; } } else { for (int i = fIdx; i <= mid; i++) { sortArr[sIdx++] = numbers[i]; } } for (int i = left; i <= right; i++) { numbers[i] = sortArr[i]; } free(sortArr); } void mergeSort(int numbers[], int left, int right) { int mid; if (left < right) { mid = (left + right) / 2; mergeSort(numbers, left, mid); mergeSort(numbers, mid + 1, right); areaMerge(numbers, left, mid, right); } } int main() { int N; scanf("%d", &N); int numbers[N]; for (int i = 0; i < N; i++) { scanf("%d", &numbers[i]); } mergeSort(numbers, 0, N - 1); for (int i = 0; i < N; i++) { printf("%d\n", numbers[i]); } }