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

11650번: 좌표 정렬하기

이 문제를 처음 시도할 떄는 크기가 N인 두 개의 배열(X, Y)을 선언하고, X의 값 기준으로 정렬할 때 Y도 같이 바꾸는 방식으로 코드를 짰다. 그러나 예상했던 것처럼 시간초과가 떴다.

#include <cstdio>

using namespace std;

int main()
{
	int N, K;
	scanf("%d", &N);
	int* coords_x = new int[N];
	int* coords_y = new int[N];
	for (int i = 0; i < N; i++) {
		scanf("%d %d", coords_x + i, coords_y + i);
	}
	bool isSorted = false;
	while (!isSorted) {
		isSorted = true;
		for (int i = 1; i < N; i++) {
			if (coords_x[i] < coords_x[i - 1]) {
				isSorted = false;
				int temp = coords_x[i];
				coords_x[i] = coords_x[i - 1];
				coords_x[i - 1] = temp;
				temp = coords_y[i];
				coords_y[i] = coords_y[i - 1];
				coords_y[i - 1] = temp;
			}
			if (coords_x[i] == coords_x[i - 1]) {
				if (coords_y[i] < coords_y[i - 1]) {
					isSorted = false;
					int temp = coords_x[i];
					coords_x[i] = coords_x[i - 1];
					coords_x[i - 1] = temp;
					temp = coords_y[i];
					coords_y[i] = coords_y[i - 1];
					coords_y[i - 1] = temp;
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		printf("%d %d\n", coords_x[i], coords_y[i]);
	}
	delete[] coords_x;
	delete[] coords_y;
	return 0;
}

코드 보기도 안 좋고, 이거를 어떻게 해야하나 고민하다가 클래스를 이용하기로 마음먹었다.

굳이 클래스를 이용하지 않고 할 수도 있겠지만, 클래스를 만들어서 하는게 깔끔할 것 같았다.

멤버 데이터로 int형 변수 x, y를 가지는 coordinate라는 클래스를 정의했다.

그리고 > 연산자에 대해 오버로딩했다. stdlib.h의 qsprt 함수를 이용하여 정렬을 시도했고, 깔끔하게 해결했다.

#include <cstdio>
#include <stdlib.h>

using namespace std;

class coordinate {
public:
	int x;
	int y;
	coordinate() : x(0), y(0) { }
	bool operator>(coordinate& rhs) {
		if (x == rhs.x) {
			return y > rhs.y;
		}
		return x > rhs.x;
	}
};

int compare(const void* lhs, const void* rhs) {
	return *(coordinate*)lhs > * (coordinate*)rhs;
}

int main()
{
	int N;
	scanf("%d", &N);
	coordinate* coord = new coordinate[N]();
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &coord[i].x, &coord[i].y);
	}
	qsort(coord, N, sizeof(coordinate), compare);
	for (int i = 0; i < N; i++) {
		printf("%d %d\n", coord[i].x, coord[i].y);
	}
	delete[] coord;
	return 0;
}