문제
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
메모: 출력할 때 endl은 버퍼를 flush 하는 역할을 겸하기 때문에 매우매우 느림!!!! '\n' 애용할것.
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 을 추가해주면 cin cout 시간 단축할 수 있다.
#include <iostream>
using namespace std;
int temp[1000000];
void Merge(int arr[], int left,int mid,int right)
{
int i = left;
int j = mid + 1;
int count = left;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
temp[count++] = arr[i++];
}
else
{
temp[count++] = arr[j++];
}
}
if (i > mid) {
for (int k = j; k <= right; k++)
temp[count++] = arr[k];
}
else {
for (int k = i; k <= mid; k++)
temp[count++] = arr[k];
}
for (int k = left; k < right + 1; k++)
{
arr[k] = temp[k];
}
}
void MergeSort(int arr[],int left,int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid+1, right);
Merge(arr, left, mid, right);
}
}
int main()
{
int N;
int arr[1000000];
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
MergeSort(arr, 0, N-1);
for (int i = 0; i < N; i++)
{
cout << arr[i] << '\n';
}
return 0;
}
728x90
반응형
'알고리즘 > solved.ac' 카테고리의 다른 글
[class2] (백준 1181) 단어 정렬 (0) | 2021.10.03 |
---|---|
[class2] (백준 7568) 덩치 (0) | 2021.10.03 |
[class2] (백준 2609) 최대공약수와 최소공배수 (0) | 2021.10.01 |
[class2] (백준 1436) 영화감독 숌 (0) | 2021.09.30 |
[class2] (백준 1018) 체스판 다시 칠하기 (0) | 2021.09.28 |