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

 

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

11650번: 좌표 정렬하기

 

---

 

문제 해결 과정

착안

정렬에 사용할 비교 연산자를 정의하여 정렬 알고리즘을 작성함으로써 문제를 해결하고자 하였다. 비교 연산자를 정의하는 방법은 연산자 오버로딩(operator overloading) 또는 비교 연산 함수 포인터를 사용하는 방법이 있는데, 이 포스팅에서는 함수 포인터를 사용하는 여러 방법 중 람다 표현식(lambda expression)을 활용해 이항 조건(binary predicate)을 정의하여 이용하는 방법을 사용하고자 하였다.

 

구현

편의상 STL의 <algorithm> 헤더에 포함되어있는 std::sort() 함수를 사용하였고, 람다 표현식을 활용해 이항 조건을 정의한 다음 함수에 전달하여 문제를 해결하였다.

* 참고) 정렬 알고리즘을 직접 구현할 때 비교 연산 함수 포인터를 사용한 케이스를 아래에 추가하였음.

 

[스포 주의] (std::sort() 함수를 사용해 정렬) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

struct Point
{
	int X;
	int Y;
};

Point Points[100000];

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

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> Points[i].X >> Points[i].Y;

	sort(&Points[0], &Points[N - 1] + 1, 
	     [](const Point& a, const Point& b)
	     {
		    if (a.X == b.X)
			    return a.Y < b.Y;

		    return a.X < b.X;
 	     });

	for (int i = 0; i < N; i++)
		cout << Points[i].X << " " << Points[i].Y << "\n";

	return 0;
}

 

 

[스포 주의] (정렬의 직접 구현 예시: 병합 정렬(merge sort)) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

struct Point
{
	int X;
	int Y;
};

Point Points[100000];
Point Sorted[100000];

void Merge(int start, int middle, int end, bool (*_Pr)(const Point&, const Point&))
{
	int left = start;
	int right = middle + 1;

	int index = left;
	while (left <= middle && right <= end)
	{
		if (_Pr(Points[left], Points[right]))
			Sorted[index++] = Points[left++];
		else
			Sorted[index++] = Points[right++];
	}

	while (left <= middle)
		Sorted[index++] = Points[left++];

	while (right <= end)
		Sorted[index++] = Points[right++];

	for (int i = start; i <= end; i++)
		Points[i] = Sorted[i];
}

void MergeSort(int start, int end, bool (*_Pr)(const Point&, const Point&))
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		MergeSort(start, middle, _Pr);
		MergeSort(middle + 1, end, _Pr);
		Merge(start, middle, end, _Pr);
	}
}

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

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> Points[i].X >> Points[i].Y;

	MergeSort(0, N - 1,
		  [](const Point& a, const Point& b)
		  {
			  if (a.X == b.X)
				  return a.Y < b.Y;

			  return a.X < b.X;
		  });

	for (int i = 0; i < N; i++)
		cout << Points[i].X << " " << Points[i].Y << "\n";

	return 0;
}

 

실행 결과

위: std::sort() 함수를 사용하여 문제를 해결한 결과, 아래: 병합 정렬 알고리즘을 직접 구현하여 해결한 결과