문제

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

입력

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

출력

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

예제 입력/출력

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> nums;

// 병합 과정
void mergeSort(int start, int mid, int end) {
	vector<int> temp;
	
	int md = mid + 1, st = start;

    // start나 mid가 끝점에 도달하면 종료
	while (start <= mid && md <= end) 
		nums[start] > nums[md] ? temp.push_back(nums[md++]) : temp.push_back(nums[start++]);

    // 나머지 남은 것들을 temp에 쭉 삽입
	while (start <= mid)
		temp.push_back(nums[start++]);
	while (md <= end)
		temp.push_back(nums[md++]);

    // temp에 있는 것을 본래의 nums 벡터로 옮김
	for (int i = st; i <= end; i++)
		nums[i] = temp[i-st];
}

// 분할과정 및 병합 함수 호출
void mergeSortSplit(int start, int end) {	
	if (start < end) {
		int mid = (start + end) / 2;

		mergeSortSplit(start, mid);
		mergeSortSplit(mid+1, end);
		mergeSort(start, mid, end);
	}
}

int main() {
	int n;

	scanf("%d", &n);
	nums.resize(n);
	
	for (int i = 0; i < n; i++)
		scanf("%d", &nums[i]);

	mergeSortSplit(0, n-1);
	
	for (vector<int>::iterator i = nums.begin(); i < nums.end(); i++)
		printf("%d\n", *i);

	return 0;
}

풀이

언젠간 정렬알고리즘을 제대로 구현해보리라 생각했지만, 그것이 오늘이었다. 위 문제를 풀기위해 정렬알고리즘 중에서 Merge Sort(합병/병합정렬) 알고리즘을 사용하였다.

Merge Sort
시간 복잡도: O(nlogn)
비교기반 정렬 알고리즘으로, 분할 정복 알고리즘의 하나.

이 문제를 풀면서 ‘시간초과’가 많이 발생하는데, 실제로 첫 제출하고 시간초과가 발생하기도 했다. 이에 대한 해결방안 참고 글이 있다. 나의 경우는 cout을 할때 개행문자(\n)가 아닌 endl을 사용해서 발생하였다. 이를 고치니 바로 시간안에 성공하였다.