[백준] 2751번 수 정렬하기 2 C++ 문제 풀이 정렬

문제

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

입력

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

출력

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

---

예제 입력 1

5

5

4

3

2

1

---

예제 출력 1

1

2

3

4

5

---

문제 풀이

#include<iostream>
using namespace std;
int N,arr[1000001];
int *arr2;

void merge(int left, int right){
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] <= arr[j]) 
			arr2[k++] = arr[i++]; 
		else
			arr2[k++] = arr[j++];
	}

	int tmp = i>mid ? j : i;
	
	while(k<=right) arr2[k++] = arr[tmp++];

	for (int i=left;i<=right;i++) arr[i] = arr2[i];
}

void partition(int left,int right){
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2; 
		partition(left, mid);
		partition(mid + 1, right);
		merge(left, right);
	}
}

int main(){
	scanf("%d",&N);
	arr2 = new int[N];
	for (int i=0;i<N;i++) scanf("%d",&arr[i]);

	partition(0, N - 1);

	for (int i=0;i<N;i++) printf("%d\n",arr[i]) ;
}

버블정렬, 선택정렬, 삽입정렬 등은 시간 복잡도가 O(n²) 이기 때문에 시간 초과가 나타납니다.

시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있기 때문에

병합정렬(Merge Sort)로 풀었습니다.

 

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

2751번: 수 정렬하기 2