[백준/11650/C] 좌표정렬하기

첫번째 시도: 좌표구조체를 만들어서 dictionary ordering을 위한 버블소트를 구현하였다

(당연히 문제의 의도가 O(n^2)이면 시간초과로 만들 의도기 때문에 실패)

#include <stdio.h>

typedef struct dict{
    int x; int y;
}DICT;


int main(){
    int N; scanf("%d",&N);
    DICT arr[N];
    for(int i=0; i<N; i++){
        scanf("%d %d",&arr[i].x,&arr[i].y);
    }
    
    DICT t;

    for (int i=0; i<N; i++){ //Dictionary Ordering
        for(int j=0; j<N-i-1; j++){
            if ((arr[j].x>arr[j+1].x) || (arr[j].x==arr[j+1].x && arr[j].y>arr[j+1].y)){
                t.x = arr[j+1].x; t.y = arr[j+1].y;
                arr[j+1].x = arr[j].x; arr[j+1].y = arr[j].y;
                arr[j].x = t.x; arr[j].y = t.y;
            }
        }
    }

    for (int i=0; i<N; i++){
        printf("%d %d\n",arr[i].x, arr[i].y);
    }
}

 

 

결론 : 퀵소트를 쓰면 O(nlogn)으로 쉽게 풀수있다 (너무 날먹인것 같지만 퀵소트 사용법을 잘 숙지해두도록하자. 퀵소트의 원리는 나중에 시간되면 올리겠지만 사실 인터넷을 뒤져보면 널린게 원리설명이다)

 

#include <stdio.h>
#include <stdlib.h>

typedef struct dict{
    int x; int y;
}DICT;

int compare(const void *pa,const void *pb){
    const DICT *a = pa; const DICT *b = pb;
    if (a->x>b->x || (a->x==b->x && a->y>b->y)) return 1;
    else return -1;
}

int main(){
    int N; scanf("%d",&N);
    DICT arr[N];
    for(int i=0; i<N; i++){
        scanf("%d %d",&arr[i].x,&arr[i].y);
    }

    qsort(arr, N, sizeof(DICT), compare);

    for (int i=0; i<N; i++){
        printf("%d %d\n",arr[i].x, arr[i].y);
    }

}