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

문제

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

입력

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

출력

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

구상

Key와 Value로 한 쌍을 묶어서 저장할 수 있는 map STL이 있다. 심지어 알아서 정렬도 해준다. 하지만 map은 중복된 키를 사용할 수 없다.

multimap을 이용하면 중복된 키는 사용할 수 있지만 기본 옵션으로는 키나 값 둘 중 한 가지 값으로만 정렬이 가능하다.

문제에서 제시하는 것처럼 x 좌표과 같을 때 y 좌표 순으로 정렬하려면 조금 더 복잡한 과정을 거쳐야 한다.

 

이런 문제를 편하게 해결할 수 있는 건 multiset이다. 알아서 다 정렬해준다.

set에도 map처럼 한 쌍을 집어넣을 수 있다. pair를 활용하면 된다.pair는 두 객체를 하나의 객체로 취급할 수 있게 묶어주는 클래스다. set에 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;
}