BOJ 백준온라인져지 11651 좌표 정렬하기 2 풀이

예제 입력 

5
0 4
1 2
1 -1
2 2
3 3

예제 출력 

1 -1
1 2
2 2
3 3
0 4

y를 오름차순으로 정렬하는데, y가 같으면 x의 오름차순으로 정렬하는 문제.

quick sort를 사용하면 nlgn인데,

y, x를 둘다하게되면

시간초과여서

꼼수를 부렸다.

	#include <cstdio>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/11651
	* BOJ 백준온라인져지 11651 좌표 정렬하기 2 풀이
	*/
	using namespace std;
	void quickSort(vector<long> &arr, int left, int right) {
	int i = left, j = right;
	long pivot = arr[(left + right) / 2];
	long temp;
	do {
	while (arr[i] < pivot)
	i++;
	while (arr[j] > pivot)
	j--;
	if (i <= j) {
	temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	i++;
	j--;
	}
	} while (i <= j);
	/* recursion */
	if (left < j)
	quickSort(arr, left, j);
	if (i < right)
	quickSort(arr, i, right);
	}
	int main(){
	int T;
	scanf("%d",&T);
	vector<long> pointList;
	while(T--){
	long x1,y1;
	scanf("%ld%ld",&x1,&y1);
	pointList.push_back((y1+100000)*1000000+(x1+100000));
	}
	quickSort(pointList, 0, pointList.size()-1);
	for(int i = 0, size = pointList.size(); i<size; i++){
	long y = pointList[i] / 1000000 - 100000;
	long x = pointList[i] % 1000000 - 100000;
	printf("%ld %ld\n",x,y);
	}
	return 0;
	}

view raw BOJ_11651.cpp hosted with ❤ by GitHub