[Algorithm][C언어] 백준 11651번: 좌표 정렬하기 2

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

11651번: 좌표 정렬하기 2

---

문제 요약

2차원 평면 위의 점 N개가 주어진다. 
좌표를 y좌표가 증가하는 순으로, 
y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성해라.

(y좌표가 작은 순서부터 출력, y좌표가 같을 시 x좌표가 작은 순서부터 출력)

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000)

좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력

코드

#include <stdio.h>
#include <stdlib.h> //문자열 변환 함수 포함

/* 구조체 정의와 구조체 변수 선언 */
typedef struct point { 
	int x;
	int y;
}p;

/* 점의 x좌표와 y좌표 크기 비교 (오름차순) 함수 */
//const가 포인터 변수 앞에 붙어 포인터 변수 안에 있는 내용물 수정 X
int compare(const void * a, const void * b) { 
	p * p1 = (p *)a;
	p * p2 = (p *)b;

	if (p1->y < p2->y) { //p1의 y좌표가 p2의 y좌표보다 작다면
		return -1; //-1 반환
	}
	else if (p1->y > p2->y) { //p1의 y좌표가 p2의 y좌표보다 크다면
		return 1; //1 반환
	}
	else {
		if (p1->x < p2->x) return -1; //p1의 x좌표가 p2의 x좌표보다 작다면 -1 반환
		else if (p1->x > p2->x) return 1; //p1의 x좌표가 p2의 x좌표보다 크다면 1 반환
	}

	return 0;
}

/* 메인 함수 */
int main() {
	int N; //점의 개수 
	scanf("%d", &N); //점의 개수 입력 받기
	p *arr = (p *)malloc(sizeof(p) * N); //동적 메모리 할당

	for (int i = 0; i < N; i++) { //점의 개수만큼 반복
		scanf("%d %d", &arr[i].x, &arr[i].y); //점의 x좌표와 y좌표 배열에 입력 받기
	}

	//퀵 정렬 함수 //qsort(정렬할 배열, 요소 개수, 요소 크기, 비교 함수);
	qsort(arr, N, sizeof(p), compare); 

	for (int i = 0; i < N; i++) {//점의 개수만큼 반복
		printf("%d %d\n", arr[i].x, arr[i].y); //정렬된 배열 출력
	}
}

그냥 단순하게 for문 돌려서 y값 비교하고 y가 작은 순서대로 출력한 다음 if문을 한 번 더 사용하려고 했다.
근데 그걸 실행해보자 이상한 결과가 나와서 내 생각만큼 단순한 코드가 아님을 깨닫고 여러 번 시도해봤다.
그리고...
도저히 모르겠어서 구글링했다.
참고 링크: https://codejin.tistory.com/104

 

구글링한 결과, 내가 생각도 못했던 구조체와 퀵 정렬 함수를 사용하는 코드였다. 
그 둘을 이용하는 게 너무 오랜만이라서 구조체와 퀵 정렬 함수 개념을 다시 공부한 뒤에 코드를 분석했다.

확실히 아직 c언어에 대한 공부가 부족하다고 느꼈고, 앞으로 더 열심히 문제풀이를 진행해야겠다고 생각했다.

실행 화면

결과