[백준 10814] 나이순 정렬

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

10814번: 나이순 정렬

요구사항

1. 나이 오름차순

2. 먼저 가입한 순

 

풀이

1. 입력할때 가입한 순서를 저장하여 정렬한다.

 

#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;
 
const int PN = 23;
const int HASH_SIZE = 10000;


struct go{
    int size;
    char ch[101];
    int num;
};
go map[100001];
go buf[100001];

int n;

void merge_sort(go arr[], int len){
    if(len<2){
        return;
    }
    int i,j,mid,k;
    mid=len/2;
    i=0;
    j=mid;
    k=0;
    merge_sort(arr,mid);
    merge_sort((arr+mid),(len-mid));

    while(i<mid && j <len){
        
        if(arr[i].size < arr[j].size){
            buf[k++]=arr[i++];
        }
        
        else if(arr[i].size == arr[j].size){
          //  cout<<arr[i].size<<endl;
            if(arr[i].num > arr[j].num){
                buf[k++]=arr[j++];
            }
            else{
                buf[k++]=arr[i++];
            }

        }
        else{
            buf[k++]=arr[j++];
        }
    }

    while(i<mid){
        buf[k++]=arr[i++];
    }

    while(j<len){
        buf[k++]=arr[j++];
    }

    for(int k=0 ; k <len ; k++){
        arr[k]=buf[k];
    }

}

int main(){
    cin>>n;
    for(int i=0 ; i < n ; i++)
    {
        scanf("%d",&map[i].size);
        scanf(" %s",&map[i].ch);
        map[i].num=i;
    }
    merge_sort(map,n);
    for(int i=0 ; i < n; i++){
        printf("%d %s\n",map[i].size,map[i].ch);
    }
}