[코딩테스트]BJ11651 좌표 정렬하기2 -C++

[문제]

2차원 평면 위의 점 N개가 주어진다. 좌표를 Y좌표가 증가하는 순으로, Y좌표가 같으면 X좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

[입력]

첫째 줄에 점의 개수(1<=N<=100,000) 이 주어진다.
둘째 줄부터 N개의 줄에는 i번 점의 위치 xi와 yi가 주어진다. (-100,000<=xi,yi<=100,000)
좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

[출력]

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

[접근 방식]

이 문제는 algoritm 헤더의 sort 함수를 이용하여 풀 수 있다.
그러나 기존의 sort함수는 vector의 first만을 sort하도록 되어있다.
vector의 second 요소로 정렬을 하기 위해서는 sort함수의 세번째 인자를 살펴 봐야한다.
세번째 요소는 오름차순을 할 것인지 내림차순으로 정렬을 할 것인지 정할 수 있는 파라미터 이다.
이에 compare 함수를 새로 만들어, 두번째 수가 같으면 x 기준으로 정렬하도록 하였다.

+처음에 코드 시간초과가 났는데
endl 대신 '\n'로 바꾸었더니 해결할 수 있었다.
endl은 출력 버퍼를 비워야해서 \n보다 속도가 느리다.

[코드]

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std; 

bool compare(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.second == b.second)
		return a.first < b.first;
	else
		return a.second < b.second;
}
int main() {
	int N; 
	vector<pair<int,int>> dots;
	cin >> N; 
	for (int i = 0; i < N; i++) {
		int x, y; 
		cin >> x >> y;
		dots.push_back(make_pair(x, y));
	}

	sort(dots.begin(), dots.end(),compare);

	for (int i = 0; i < N; i++) {
		cout << dots[i].first << " " << dots[i].second << "\n";
	}
	return 0; 
}