[백준알고리즘] 11650번: 좌표 정렬하기 -C++

[백준알고리즘] 11650번: 좌표 정렬하기 -C++

11650번: 좌표 정렬하기 (acmicpc.net)

11650번: 좌표 정렬하기

예전에 파이썬으로 푼 코드가 있다. 아래의 파이썬으로 푼 내용이 포스팅되어 있다. 

이 문제 외에도 11651번 문제도 함께 있다.

[백준알고리즘] 11650, 11651번: 좌표 정렬하기, 좌표 정렬하기 2 -Python (tistory.com)

[백준알고리즘] 11650, 11651번: 좌표 정렬하기, 좌표 정렬하기 2 -Python

 

이 문제는 사실 아래에 코드에서 주석 처리한 <algorithm> 헤더에 있는 sort를 사용하면 된다. 게다가 오름차순이기 때문에 std::less<>를 사용하지 않고도 자동으로 적절하게 문제에 있는 요구조건대로 pair를 비교해 정렬해준다.

 

하지만, 직접 compare 함수를 써보기 위해 문제를 풀어봤다.

 

 

sort의 세 번째 인자에는 std::greater<>와 std::less<> 외에도 사용자가 정의한 비교 함수를 임의로 넣을 수 있다.

 

비교 함수에서는 sort에서 사용할 원소의 객체를 두 개 전달받는다. return으로는 true(1) 혹은 false(0)을 주면 된다.

sort 함수에서는 두 인자를 compare 함수의 인자로 넘기고 true와 false를 받음으로써 두 원소를 swap 할지 여부를 판단하게 된다.

sort 함수에서는 compare의 return 값이 true일 경우에는 그대로 위치를 유지하며, false를 return 할 경우에만 두 원소의 위치를 swap 한다.

 

 

이 문제에서는 std::less<>를 사용한 것처럼 \(x\)와 \(y\)가 모두 오름차순이라 결과가 같지만, 만약 \(x\)를 오름차순, \(y\)를 내림차순 등 다양한 기준을 적용할 때에는 compare 함수를 직접 작성해서 쓰는 것이 옳다.

 

---

아래는 C++ 코드다.

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

void solve(void);

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

	solve();
}

bool compare(std::pair<int, int> a, std::pair<int, int> b)
{
	if (a.first == b.first) return a.second < b.second;
	return a.first < b.first;
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<std::pair<int, int>> arr;
	for (int i = 0; i < n; i++)
	{
		int x, y;
		std::cin >> x >> y;
		arr.push_back(std::make_pair(x, y));
	}

	//std::sort(arr.begin(), arr.end());
	std::sort(arr.begin(), arr.end(), compare);

	for (int i = 0; i < n; i++)
	{
		int x, y;
		std::tie(x, y) = arr[i];

		std::cout << x << " " << y << '\n';
	}

}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다