알고리즘/백준
백준 11650_좌표 정렬하기
래울
2020. 11. 1. 19:23
https://www.acmicpc.net/problem/11650
11650번: 좌표 정렬하기
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
www.acmicpc.net
좌표 정렬 하는 문제이다.
#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)