백준 2751: 수 정렬하기 2(C++, 실버5)

문제

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

성공 코드

  머지 소트를 연습하기 위해서 머지 소트를 구현해 봤다. 첫 제출에 시간 초과로 실패가 떴는데, 그 이유는 입출력 속도 탓이었다. 버릇처럼 endl을 사용하는 바람에 시간 초과가 떴고, endl 대신 "\n"을 넣어서 성공할 수 있었다.

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

vector<int> nums;
vector<int> temp;

void MergeSort(int start, int end)
{
	if (end - start < 1)
		return;
	int middle = start + (end - start) / 2;
	MergeSort(start, middle);
	MergeSort(middle + 1, end);
	for (int i = start; i <= end; i++)
		temp[i] = nums[i];

	int k = start;
	int idx1 = start, idx2 = middle + 1;
	while (idx1 <= middle && idx2 <= end)
	{
		if (temp[idx1] < temp[idx2])
			nums[k++] = temp[idx1++];
		else nums[k++] = temp[idx2++];
	}
	while (idx1 <= middle)
		nums[k++] = temp[idx1++];
	while (idx2 <= end)
		nums[k++] = temp[idx2++];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	nums.resize(n);
	temp.resize(n);

	for (int i = 0; i < n; i++)
		cin >> nums[i];

	MergeSort(0, n - 1);

	for (int i = 0; i < n; i++)
		cout << nums[i] << "\n";
}