[백준/C++] 11650번: 좌표 정렬하기

문제

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

---

문제 요약

2차원 평면 위의 점 N개가 주어졌을 때, x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순으로 정렬하고 점을 순서대로 출력한다.

---

코드

#include <iostream>
#include <tuple>
#include <queue>
using namespace std;

int n;

priority_queue<tuple<int, int>> q;

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;

		cin >> x >> y;

		q.push({ -x, -y });
	}

	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.top();

		q.pop();

		cout << -x << " " << -y << "\n";
	}
	
}

---

코드 설명

Priority Queue를 이용하여 문제를 해결한다.

 

점들을 입력 받을 때마다, 우선순위 큐에 요소를 하나씩 삽입한다.

 

삽입할 때마다 큐 안의 내용은 자동으로 내림차순 정렬된다.

 

문제에서 오름차순을 요구하고 있으므로, 삽입 전에 점의 좌표에 -를 붙여 삽입한다.

 

물론, 큐에서 뺄 때 다시 -를 붙여주어야한다.

---

고찰

단순한 기준의 정렬이기 때문에, 우선순위 큐를 통해서 해결했다.

 

하지만, 좀 더 복잡한 정렬은 sort의 세 번째 인자(compare)를 이용해야한다.

 

bool compare()는 첫 번째 인자와 두 번째 인자를 비교한다.

 

1. true인 조건은 첫 번째 인자가 두 번째 인자보다 더 앞에 있다고 간주하는 상황이다.

 

2. false인 조건은 첫 번째 인자가 두 번째 인자보다 더 뒤에 있다고 간주하는 상황이다.

 

< 위 문제를 sort함수를 사용하여 푼 코드 >

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

using namespace std;

int n;

vector<tuple<int, int>> v;

// a : 1번째 수, b : 2번째 수
bool compare(tuple<int, int> a, tuple<int, int> b) {
	if (get<0>(a) == get<0>(b)) { // get은 튜플의 요소를 추출하는 함수
		return get<1>(a) < get<1>(b);
	}
	return get<0>(a) < get<0>(b);
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;

		cin >> x >> y;

		v.push_back({ x, y });
	}

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

	for (int i = 0; i < v.size(); i++) {
		int x, y;
		tie(x, y) = v[i];

		cout << x << " " << y << "\n";
	}
}

 

C++에서의 복잡한 정렬 문제를 더 풀어봐야 할 것 같다.