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

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

11650번: 좌표 정렬하기

 

[풀이 후기]
난이도 : ★★☆☆ (Advanced)
문제 종류 : Sort
해결 방법 : Merge Sort

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

---

 

문제

 

 

 

문제분석

1. 최대 10만개의 좌표를 오름차순으로 정렬해야하는 문제이다. 
2. 점의 개수와 좌표값이 모두 int 범위 안에 들어온다. 
3. 좌표를 정렬할 때, 비교 연산자 오버로딩을 활용하면 편리하다. 

---

 

접근 방법

이 문제의 핵심은 "어떻게 2차원 좌표를 빠르게 정렬할 것인가?" 이다. 

 

 

이부분을 해결하기 위해서는 2가지가 필요하다. 

1. 좌표를 정렬할 Sorting 알고리즘
2. Sorting 알고리즘에서 사용할 좌표 비교 방법

 

 

 

1. 좌표를 정렬할 Sorting 알고리즘

우선, 여러가지 정렬 방법이 있겠지만, 나는 Merge Sort를 이용하여 해결했다. 

 

* Merge Sort는 아래 포스팅을 참고하자. 

[알고리즘][정렬][C/C++] Merge Sort (병합정렬)

[알고리즘][정렬][C/C++] Merge Sort (병합정렬)

 

 

 

2. Sorting 알고리즘에서 사용할 좌표 비교 방법

Merge Sort 또는 Heap Sort, Bubble Sort 등 2개의 수를 비교해서 정렬하는 알고리즘들에서, 

비교 연산자 오버로딩을 활용하면 수가 아닌 좌표를 비교할 수 있다. 

 

* 연산자 오버로딩(Operator Overloading) : 기존의 연산 기능이 아닌 다른 기능을 위해, 함수를 재정의 하는 것

 

아래 코드를 보면서 비교해보자. 

 

① 일반 코드

struct P {
	int x, y;
};

int pointComp(P a, P b) {
	if (a.x > b.x) 
		printf("a가 b보다 크다.\n");
	else if (a.x == b.x) {
		if(a.y >= b.y) printf("a가 b보다 크다.\n");
		else printf("a가 b보다 작다.\n");
	}
	else
		printf("a가 b보다 작다.\n");
}

 

② 비교연산자 오버로딩

struct P {
	int x, y;

	int operator<= (P a) {	// "<=" 연산자 오버로딩
		if (x < a.x) return 1;
		else if (x == a.x) return y <= a.y ? 1 : 0;
		else return 0;
	}
};

int pointComp(P a, P b) {
	if(a <= b)
		printf("a가 b보다 작다.\n");
	else
		printf("a가 b보다 크다.\n");
}

 

"<=" 연산자를 오버로딩하여, pointComp 함수가 간결해진 것을 확인할 수 있다. 

 

 

---

 

코드

Merge Sort 에서 연산자 오버로딩을 적용하여 문제를 해결한 전체 코드이다. 

#include <stdio.h>

const int LM = 100000;
int N;

struct P {
	int x, y;

	int operator<= (P a) {	// "<=" 연산자 오버로딩
		if (x < a.x) return 1;
		else if (x == a.x) return y <= a.y ? 1 : 0;
		else return 0;
	}
}A[LM + 5], trr[LM + 5];

void mergeSort(int s, int e) {
	if (s >= e) return;	// 1. base condition

	int mid = (s + e) / 2;	// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	int i = s, j = mid + 1, k = s;	// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] <= A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];
	while (j <= e) trr[k++] = A[j++];

	for (i = s; i <= e; i++) A[i] = trr[i];	// 4. copy
}

int main() {
	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		A[i] = { x, y };
	}

	mergeSort(1, N);

	for (int i = 1; i <= N; i++) {
		printf("%d %d\n", A[i].x, A[i].y);
	}

	return 0;
}

 

---

 

제출 결과

백준 제출 결과