[C++] 백준 11650번 좌표 정렬하기

1. 문제이해

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

11650번: 좌표 정렬하기

 

2차원 평면위의 좌표들을 x좌표가 증가하는 순으로,

x좌표가 같다면 y좌표가 증가하는 순으로 정렬하는 프로그램을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

2차원 평면 좌표를 x좌표 순으로 정렬하되, x좌표가 같다면 y좌표 순으로 정렬하는 것이 목표이다.

각 점에서의 x좌표, y좌표를 모두 입력받아 순서가 뒤바뀌는 일 없이 정렬해야 하므로,

안정 정렬(stable_sort)를 이용해주기로 했다.

(안정정렬은 동일한 값에 대해 기존의 순서가 유지되는 정렬, 즉, 원래 존재하던 순서를 중시하는 정렬이다.)

 

안정 정렬을 통해 기존 좌표쌍들을 바꾸지 않으면서, 문제에서 요구하는 방식으로 정렬해주기 위해

아래 stable_sort의 인자들 중 cmp에 해당하는 부분의 함수를 살짝 수정해주었다.

 

stable_sort(정렬을 시작할 부분, 정렬을 끝낼 부분, cmp);

 

해당 부분의 cmp는 정렬을 어떻게 할 것인가에 대한 규칙을 나타내는 부분으로,

해당 부분에 x좌표 증가순으로 정렬하되,

x좌표가 같다면 y좌표 순으로 증가하도록 정렬한다는 조건을 포함하는 함수를 작성해 넣어주면 된다.

자세한 구현은 아래 소스코드를 참고하자.

 

 

 

3. 소스코드

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

class coordinate {
public:
	int x;		// x좌표
	int y;		// y좌표
};

bool cmp(coordinate a, coordinate b) {
	// x좌표가 증가하는 순으로 정렬하되, 
	// x좌표가 같으면 y좌표가 증가하는 순서대로 정렬
	if (a.x == b.x) {         
		return a.y < b.y;
	}

	else {
		return a.x < b.x;
	}
}

coordinate* c = new coordinate[100000];

int main() {
	int N;
	int numx, numy;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> c[i].x >> c[i].y;
	}

	stable_sort(c, c + N, cmp);

	for (int i = 0; i < N; i++) {
		cout << c[i].x << " " << c[i].y << "\n";
	}

	return 0;
}

 

2차원 공간에서의 점을 나타내는 class coordinate를 선언하고,

x좌표와 y좌표에 해당하는 변수 x, y를 선언해준다.

(이차원 배열로 선언해도 무관하지만, 필자는 배열의 크기가 너무 커질것 같아 class로 선언해주었다.)

 

그리고, 2. 문제풀이에서 이야기한 cmp 부분에 해당하는 함수를 작성해주었다.

cmp함수는 x좌표 증가순으로 정렬하되,

if문을 통해, 만약 x좌표가 같다면 y좌표 순으로 증가한다는 조건을 포함해 위와 같이 작성해주었다.

 

이후 메인함수에서는 좌표의 총 갯수를 입력받고, 각 좌표의 x, y 좌표를 입력받은 뒤,

필자가 작성한 cmp함수의 조건에 맞게 안정정렬(stable_sort)를 수행 후, 출력해주었다.

 

 

---

12월의 첫 문제다.🥰

여름부터 시작한 문제풀이였는데, 어느새 겨울이라니 감회가 조금 새롭기도 하고..

앞으로도 꾸준히 문제를 풀 수 있게 노력해야지💪