[C++] 백준 11651. 좌표 정렬하기2

문제

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

입력

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

출력

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

구상

11650번 문제인 '좌표 정렬하기'를 해결할 때 mutiset과 pair를 활용했다.

#include <iostream>
#include <set>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int number;
	cin >> number;

	multiset<pair<int, int>> location;
	for (int i = 0; i < number; i++) {
		int num1, num2;
		cin >> num1 >> num2;
		location.insert(pair<int, int>(num1, num2));
	}
	
	for (auto it = location.begin(); it != location.end(); it++) {
		cout << it->first << " " << it->second << "\n";
	}

	return 0;
}

 

pair에 들어가는 첫 번째 인자를 first, 두 번째 인자를 second라 하는데, 기본적으로 first 오름차순, first가 같으면 second 오름차순으로 정렬되도록 설정되어 있다. 

 

이번 문제에서는 second 오름차순, second가 같으면 first 오름차순으로 정렬해야 한다. 따라서 multiset에 추가로 비교함수 인자를 넣어주어야 한다.

 

struct cmp {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
		if (a.second == b.second) {	//second가 같으면
			return a.first < b.first;	//first 오름차순
		}
		return a.second < b.second;	//second 오름차순
	}
};

struct cmp {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) const

이 부분은 pair 내에 있는 operator를 오버로딩하기 위함이다. 

이제 함수 내부에서 정렬 방법을 정하면 된다. 

second가 기준이 되어야 하므로, second가 같은 경우에는 first가 작은 순서대로 정렬하고, 아니면 second가 작은 순으로 정렬한다.

 

이 함수를 multiset의 인자로 넣어주면 된다.

multiset<pair<int, int>, cmp> location;

 

코드

 

#include <iostream>
#include <set>

using namespace std;

struct cmp {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
		if (a.second == b.second) {
			return a.first < b.first;
		}
		return a.second < b.second;
	}
};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int number;
	cin >> number;

	multiset<pair<int, int>, cmp> location;
	for (int i = 0; i < number; i++) {
		int num1, num2;
		cin >> num1 >> num2;
		location.insert(pair<int, int>(num1, num2));
	}
	for (auto it = location.begin(); it != location.end(); it++) {
		cout << it->first << " " << it->second << "\n";
	}

	return 0;
}