[백준] 11650. 좌표 정렬하기

: solved.ac class 2 - silver 5

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

11650번: 좌표 정렬하기

 

 

예제 입력

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

 

예제 출력

1 -1
1 1
2 2
3 3
3 4

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int x, y;
}point;

int compare(const void* a, const void* b) {
	point* p1 = (point*)a;
	point* p2 = (point*)b;

	if (p1->x < p2->x) return -1;
	else if (p1->x > p2->x) return 1;
	else {
		if (p1->y < p2->y) return -1;
		else return 1;
	}

	return 0;
}

int main() {
	int n;
	point* list;

	scanf("%d", &n);
	list = (point*)malloc(n * sizeof(point));

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &list[i].x, &list[i].y);
	}

	qsort(list, n, sizeof(point), compare);

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

	return 0;
}

---

해설

 

: 구조체로 점의 좌표를 구현한 뒤, 변형한 compare 함수로 내장함수인 퀵 소트를 이용한다.

 

 

구조체로 점을 구현한다. int형으로 x와 y 필드를 각각 선언해 주고, 여러 개의 점을 일련으로 처리하기 위해 list를 만들어 케이스의 갯수인 n만큼의 공간을 할당해 준다.

n의 횟수만큼 list에 매달린 구조체들의 필드에 x좌표와 y좌표를 각각 입력받고,

내장함수인 qsort에 이 list와 자료 갯수 n, 자료 크기 sizeof(point), 비교함수 compare를 넘겨준 뒤

그대로 출력하면 점이 정렬되어 나온다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int x, y;
}point;

int main() {
	int n;
	point* list;

	scanf("%d", &n);
	list = (point*)malloc(n * sizeof(point));

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &list[i].x, &list[i].y);
	}

	qsort(list, n, sizeof(point), compare);

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

	return 0;
}

 

비교함수는 더욱 간단하다. 비교할 두 대상을 포인터 형태로 넘겨받고,

x 필드의 크기를 비교하여 앞의 것이 더 작으면 -1, 더 크면 1을 반환한다.

만약 x 필드가 같다면 y 필드를 비교하여 같은 식으로 -1과 1을 반환하게 한다.

모두 같다면 0을 반환하게 될 것이다.

//비교 함수
int compare(const void* a, const void* b) {
	point* p1 = (point*)a;
	point* p2 = (point*)b;

	//x를 먼저 비교해서 순서를 정하고
	if (p1->x < p2->x) return -1;
	else if (p1->x > p2->x) return 1;
	//x가 같은 경우 y를 비교
	else {
		if (p1->y < p2->y) return -1;
		else return 1;
	}

	return 0;
}