[BOJ] 11650번 : 좌표 정렬하기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
const int MXN = 100'002;
vector<pair<int, int>> v(MXN+2);
vector<pair<int, int>> temp(MXN + 2);
void merge(int st, int en) {
	int mid = (st + en) / 2;
	int lidx = st; 
	int ridx = mid; 

	for (int i = st; i < en; i++) {
		if (lidx == mid) temp[i] = v[ridx++];
		else if (ridx == en) temp[i] = v[lidx++];
		else if (v[lidx].first == v[ridx].first) {
			if (v[lidx].second <= v[ridx].second) temp[i] = v[lidx++];
			else temp[i] = v[ridx++];
		}
		else if (v[lidx].first < v[ridx].first) temp[i] = v[lidx++];
		else temp[i] = v[ridx++];
	}
	for (int i = st; i < en; i++) {
		v[i] = temp[i];
	}
}
void merge_sort(int st, int en) {
	if (st + 1 >= en) return; 
	int mid = (st + en) / 2;
	merge_sort(st, mid);
	merge_sort(mid, en);
	merge(st, en);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n;

	for (int i = 0; i < n; i++) {
		pair<int, int> s;
		cin >> s.first >> s.second; 
		v[i] = s;
	}
	merge_sort(0, n); 
	for (int i = 0; i < n; i++) {
		cout << v[i].first << ' ' << v[i].second << '\n'; 
	}

}

 

3. solution 2 :

// Authored by : std-freejia
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/5a5a95bcc0644b138ad6850e5db9e87a
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int n, a, b;
pair<int, int> p[100004];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> p[i].X >> p[i].Y;
  }
  sort(p, p + n);
  for(int i = 0; i < n; i++) cout << p[i].X << ' ' << p[i].Y << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0E/solutions/11650.cpp

basic-algo-lecture/0x0E/solutions/11650.cpp at master · encrypted-def/basic-algo-lecture

sort를 이용하면, x값이 같은 경우, y값을 기준으로 오름차순 정렬을 한다.