[백준 11650] 좌표 정렬하기

좌표를 저장하는 구조체를 저장하고, 주어진 조건대로 정렬해줄 비교 함수를 작성하면 끝이다.

내가 정의한 구조체를 정렬할 때 비교함수를 직접 작성해도 되고 구조체 안에서 연산자 오버로딩을 해주면 된다.

 

1. 비교함수 작성

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// 좌표를 저장한 구조체
struct Pos {
	int x;
	int y;
};
// 비교함수
bool compare(const Pos& p1, const Pos& p2) {
	if (p1.x == p2.x) return p1.y < p2.y;
	return p1.x < p2.x;
}

Pos pos[100001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    
	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) cin >> pos[i].x >> pos[i].y;

	sort(pos, pos + n, compare);

	for (int i = 0; i < n; ++i) cout << pos[i].x << ' ' << pos[i].y << '\n';

	return 0;
}

---

2. operator< 정의 (연산자 오버로딩)

#include <bits/stdc++.h>

using namespace std;

struct Pos {
	int x;
	int y;

	bool operator< (Pos& p) {
		if (this->x == p.x) return this->y < p.y;
		return this->x < p.x;
	}
};

Pos pos[100001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    
	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) cin >> pos[i].x >> pos[i].y;
	// operator<를 정의해주었기 때문에 따로 비교함수가 필요없다
	sort(pos, pos + n);

	for (int i = 0; i < n; ++i) cout << pos[i].x << ' ' <<  pos[i].y << '\n';

	return 0;
}

---

꿀팁으로 STL에서 제공하는 pair 클래스를 이용하면 굳이 구조체를 정의하지 않아도 된다. 

알고리즘 문제를 해결하다보면 자주 쓰게 되기 때문에 사용법에 익숙해지는 걸 추천드린다.

 

3. pair 클래스

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

pair<int, int> pos[100001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    
	int n;
	cin >> n;
    
	for (int i = 0; i < n; ++i) cin >> pos[i].first >> pos[i].second;
    
	sort(pos, pos + n);
    
	for (int i = 0; i < n; ++i) cout << pos[i].first << ' ' <<  pos[i].second << '\n';
    
	return 0;
}

Pair로 선언된 배열을 정렬할 때 비교함수를 안넣게 되면

1. first를 기준으로 오름차순으로 정렬
2. first가 같다면 second를 기준으로 오름차순 정렬

이렇게 정렬해준다. 물론 비교 함수를 따로 작성해주어도 된다.