백준 11650_좌표 정렬하기

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

11650번: 좌표 정렬하기

 

좌표 정렬 하는 문제이다.

#include <stdio.h>
int main()
{
        int N;
        scanf("%d", &N);
        int arr[N][2];
        int i,j;
        for(i=0; i<N; i++)
                scanf("%d %d", &arr[i][0], &arr[i][1]);
        int min_index=0;
        int tx, ty;
        for(i=0; i<N; i++){
                min_index=i;
                for(j=i; j<N; j++){
                        if(arr[min_index][0] > arr[j][0]){
                                min_index=j;
                        }
                        else if(arr[min_index][0] == arr[j][0]){
                                if(arr[min_index][1] > arr[j][1])
                                        min_index=j;
                        }
                }
                tx = arr[i][0];
                ty = arr[i][1];
                arr[i][0] = arr[min_index][0];
                arr[i][1] = arr[min_index][1];
                arr[min_index][0] = tx;
                arr[min_index][1] = ty;

                //for(j=0; j<N; j++)
                //      printf("%d. %d %d \n",i,arr[j][0],arr[j][1]);

        }
        for(i=0; i<N; i++)
                printf("%d %d\n", arr[i][0], arr[i][1]);
        return 0;
}

처음에 위와 같이 그냥 c 선택정렬로 했더니, 시간 초과 ;....

크기가 100000이라 O(n^2)이면 시간초과가 난다.

 

따라서, quick sort를 이용하거나, c++에서 #include <algorithm> 로 sort()함수등을 사용해서 해결가능하다.

 

quick sort : O(n*logn)