[백준 11651]좌표 정렬하기2

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

11651번: 좌표 정렬하기 2

1/7일 풀었던 문제

 

요구사항

1. y오름차순

2. x오름차순

 

풀이

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].num < arr[j].num){
            buf[k++]=arr[i++];
        }
        
        else if(arr[i].num == arr[j].num){
          //  cout<<arr[i].size<<endl;
            if(arr[i].size < arr[j].size){
                buf[k++]=arr[i++];
            }
            else{
                buf[k++]=arr[j++];
            }

        }
        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 %d",&map[i].size,&map[i].num);
    }
    merge_sort(map,n);
    for(int i=0 ; i < n; i++){
        printf("%d %d\n",map[i].size,map[i].num);
    }
}