[정렬] BOJ 2751번 수 정렬하기2

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

2751번: 수 정렬하기 2

- 문제파악

[https://www.acmicpc.net/problem/2750] 와 같은 문제지만 N의 최대 개수가 시간 초과하기 딱 좋다.

 

- 정답

 

1. STL sort함수 활용

#include "bits/stdc++.h"

using namespace std;

int arr[1000001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;
    for(int i = 0 ; i < n; i++)
        cin>>arr[i];
    
    sort(arr,arr+n);
    
    for(int i = 0 ; i < n; i++)
        cout<<arr[i]<<"\n";
    
    
}

 

2. Merge Sort 사용

#include "bits/stdc++.h"

using namespace std;

int arr[1000001];
int tmp[1000001];

void merge(int s, int e)
{
    //반으로 나눠서 두개의 배열이 있는거 처럼 머지
    int m = (s+e)/2;
    int idxa = s;
    int idxb = m;
    
    for(int i = s ; i < e ; i++)
    {
        if(idxb == e) tmp[i] = arr[idxa++];
        else if(idxa == m) tmp[i] = arr[idxb++];      
        else if(arr[idxa] > arr[idxb]) tmp[i] = arr[idxb++];
        else tmp[i] = arr[idxa++];
    }
    
    for(int i = s ; i < e ; i++)
        arr[i] = tmp[i];
    
}

void merge_sort(int s, int e)
{
    if(e-s == 1) return;
    int m = (s+e)/2;
    merge_sort(s,m);
    merge_sort(m,e);
    merge(s,e);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;
    for(int i = 0 ; i < n; i++)
        cin>>arr[i];
    
    merge_sort(0,n);
    
    for(int i = 0 ; i < n; i++)
        cout<<arr[i]<<"\n";
    
    
}