C++ / 11651 / 좌표 정렬하기 2 ( 정렬 )

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

문제 요약

2차원 평면 위의 점 N개가 주어 집니다.

좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성해야합니다.

문제 풀이

1. 점의 개수를 입력받습니다.

2. 점들을 2차원 배열로 입력받습니다.

3. 정렬을 하는데 sort함수의 인자로 cmp함수를 만들어서 넣습니다.

4. cmp함수는 현재 진행중인 정렬의 새로운 조건인 함수입니다. 2차원 배열을 넣었을 때 비교할 1차원 배열 2개로 쪼개서 받습니다.

v = {{1, 1},  {2, 2}} 를 쪼개지면

v1 = {1, 1}v2 = {2, 2}와 같이

5. 우리는 뒤에 숫자 기준으로 정렬을 하고 싶기 때문에 뒤에 숫자 ( 1번 인덱스 )가 같을 경우엔 앞에 숫자 ( 0 번 인덱스 )를 기준으로 비교하고 뒤에 숫자가 다를 경우에 뒤에 숫자 기준으로 비교해서 반환합니다. 

주의할 점

난이도가 낮은 문제라 아무 생각 없이 pair로 만든 다음에 정렬을 하였으나 그러면 앞에 숫자 기준으로 정렬이 되어 틀린 답이 됩니다.

그러다보니 뒤에 숫자 기준으로 정렬하는 방법을 찾아보게 되었는데, 좋은 계기가 된 문제 같아 정리해봅니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
vector<vector<int>>v;

bool cmp(vector<int>& v1, vector<int>& v2)
{
	if (v1[1] == v2[1])
	{
		return v1[0] < v2[0];

	}
	else
	{
		return v1[1] < v2[1];
	}
}

int main()
{
	cin >> n;
	v.resize(n, vector<int>(2));
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v[i][0] = a;
		v[i][1] = b;

	}
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < n; i++)
	{
		cout << v[i][0] << " " << v[i][1] << "\n";
	}
	return 0;
}

예제 1

5
0 4
1 2
1 -1
2 2
3 3

결과 1