[정렬] BOJ 10814번 나이순 정렬

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

10814번: 나이순 정렬

- 문제 파악

가입한 회원 순서대로 나이와 이름이 입력된다. 이때 나이에 대해 오름차순으로 출력하라. 단, 나이가 같을 경우 가입한 순서대로 출력한다.

 

- 정답

#include "bits/stdc++.h"

using namespace std;

pair<int,string> arr[100001];
pair<int,string> tmp[100001];


void merge(int s, int e)
{
    int m = (s+e)/2;
    int idx_a = s, idx_b = m;
    
    for(int i = s ; i < e ; i++)
    {
        if(idx_a == m) tmp[i] = arr[idx_b++];
        else if(idx_b == e) tmp[i] = arr[idx_a++];
        else if(arr[idx_a].first > arr[idx_b].first) tmp[i] = arr[idx_b++];
        else if(arr[idx_a].first < arr[idx_b].first) tmp[i] = arr[idx_a++];
        else
        {
            if(idx_a > idx_b) tmp[i] = arr[idx_b++];
            else tmp[i] = arr[idx_a++];
        }
        
    }
    
    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()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int n;
    cin>> n;
     
    for(int i = 0 ; i < n ; i++)
        cin>>arr[i].first >> arr[i].second;
    
    merge_sort(0,n);
    
    for(int i = 0 ; i < n ; i++)
        cout<<arr[i].first << " " << arr[i].second << "\n";
    
}