2751번 (silver 5)

https://www.acmicpc.net/problem/2751

간단한 정렬 문제이다. 병합 정렬로 풀어보았다.

 

#include <iostream>
#include <vector>

using namespace std;

void mergeSort(vector<int>&, int, int);
int main() {
	cin.tie(0)->sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int> arr(N, 0);

	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
	}

	mergeSort(arr, 0, N - 1);

	for (auto& it : arr)
		cout << it << '\n';

	return 0;
}

void mergeSort(vector<int>& arr, int s, int e) {
	static vector<int>tmp = arr;
	if (e - s < 1) {
		return;
	}
	int m = (s + e) / 2;
	mergeSort(arr, s, m);
	mergeSort(arr, m + 1, e);

	for (int i = s; i <= e; ++i) {
		tmp[i] = arr[i];
	}

	int i = s;
	int j = m + 1;
	while (i <= m && j <= e) {
		if (tmp[i] < tmp[j]) {
			arr[s++] = tmp[i++];
		}
		else {
			arr[s++] = tmp[j++];
		}
	}

	while (i <= m) arr[s++] = tmp[i++];
	while(j <= e) arr[s++] = tmp[j++];
}