[백준 2751번][C++] 수 정렬하기 2

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

void Merge(int* v,int* temp, int left, int mid, int right)
{
	int l_index = left;
	int r_index = mid + 1;
	int insert_index = left;

	//vector<int> temp(v.size());
	//int* temp = new int[1000000];

	while (l_index <= mid && r_index <= right)
	{
		if (v[l_index] <= v[r_index])
		{
			temp[insert_index] = v[l_index];
			l_index++;
		}
		else
		{
			temp[insert_index] = v[r_index];
			r_index++;
		}

		insert_index++;
	}

	if (l_index > mid)
	{
		for (int i = r_index; i <= right; i++)
		{
			temp[insert_index] = v[i];
			insert_index++;
		}
	}
	else
	{
		for (int i = l_index; i <= mid; i++)
		{
			temp[insert_index] = v[i];
			insert_index++;
		}
	}

	for (int i = left; i <= right; i++)
	{
		v[i] = temp[i];
	}
}

void MergeSort(int* v, int* temp, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;

		MergeSort(v, temp, left, mid);
		MergeSort(v, temp, mid + 1, right);

		Merge(v, temp, left, mid, right);
	}
}

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	//vector<int> v(N);
	int* arr = new int[N];
	int* temp = new int[N];

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

	MergeSort(arr, temp, 0, N - 1);

	//for (int i = 0; i < v.size(); i++) cout << v[i] << "\n";
	for (int i = 0; i < N; i++) cout << arr[i] << "\n";

	return 0;
}

---

<풀이과정>

1. 입력을 받을 배열 arr과 임시로 담을 배열 temp를 선언

2. 합병정렬을 이용해 풀어준다.

---

<코멘트>

퀵정렬로 풀었는데 시간초과 -> 병합정렬로 풀었는데 시간초과 -> 병합정렬의 벡터를 배열로 바꾸고 나서야 통과했다.

힘든 싸움이었다...ㅋㅋㅋ

---

<제출결과>