(C) 백준 11650 - 좌표 정렬하기

백준 11650

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

11650번: 좌표 정렬하기

 

1. 문제 설명

 

입력받은 좌표를 오름차순으로 정렬하는 문제.

 

단, x의 좌표 값이 같은 경우에는 y좌표에 따라 오름차순으로 정렬한다.

 

2. 문제 풀이

 

좌표 값을 저장할 구조체를 선언한다.

 

//좌표값 저장할 구조체
typedef struct coor {
	int x;
	int y;
}coor;

 

초기에는 중첩 반복문으로 선택정렬의 방법을 사용하여 정렬을 하였지만 시간초과 메시지가 뜬다.

 

//오름차순 정렬
for (int i = 0; i < n - 1; i++) {
    coor* temp = &coorArr[i];
    for (int j = i + 1; j < n; j++) {
        if (temp->x > coorArr[j].x) {
            temp = &coorArr[j];
        }
        //x좌표 값이 같은 경우 -> y좌표 오름차순 정렬
        else if (temp->x == coorArr[j].x && temp->y > coorArr[j].y) {
            temp = &coorArr[j];
        }
    }
    //좌표 값이 바껴야 하는 경우 -> swap
    if (!(temp->x == coorArr[i].x && temp->y == coorArr[i].y)) {
        swap(&coorArr[i], temp);
    }
}

 

즉, 시간복잡도 O(n^2)보다 더 빠른 알고리즘이 필요하다는 것이다.

 

그래서  어떤 경우에도 상관없이 시간 복잡도가  O(n log n)인 합병 정렬을 사용한다.

 

void merge(int p, int q, int r) {
	int i = p, j = q + 1, k = p;
	coor* tmp = (coor*)malloc(sizeof(coor)*n); //데이터 저장할 배열
    //좌표 오름차순으로 정렬
	while (i <= q && j <= r) {
		if (coorArr[i].x <= coorArr[j].x) {
			if (coorArr[i].x == coorArr[j].x && coorArr[i].y > coorArr[j].y) {
				tmp[k++] = coorArr[j++];
			}
			else {
				tmp[k++] = coorArr[i++];
			}
		}
		else tmp[k++] = coorArr[j++];
	}
	while (i <= q) tmp[k++] = coorArr[i++];
	while (j <= r) tmp[k++] = coorArr[j++];
	for (int a = p; a <= r; a++) coorArr[a] = tmp[a];
	free(tmp);	//메모리 해제
}
void mergeSort(int p, int r) {
	int q;
	if (p < r) {
		q = (p + r) / 2;
		mergeSort(p, q);
		mergeSort(q + 1, r);
		merge(p, q, r);
	}
}

 

 

3. 전체 코드

 

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)
int n;
//좌표 구조체
typedef struct coor {
	int x;
	int y;
}coor;
coor* coorArr;	//구조체 배열
//구조체 SWAP 함수
void swap(struct coor* a, struct coor* b) {
	struct coor temp = *a;
	*a = *b;
	*b = temp;
}
//합병 정렬
void merge(int p, int q, int r) {
	int i = p, j = q + 1, k = p;
	coor* tmp = (coor*)malloc(sizeof(coor) * n); // 새 배열
	while (i <= q && j <= r) {
		if (coorArr[i].x <= coorArr[j].x) {
			if (coorArr[i].x == coorArr[j].x && coorArr[i].y > coorArr[j].y) tmp[k++] = coorArr[j++];
			else tmp[k++] = coorArr[i++];
		}
		else tmp[k++] = coorArr[j++];
	}
	while (i <= q) tmp[k++] = coorArr[i++];
	while (j <= r) tmp[k++] = coorArr[j++];
	for (int a = p; a <= r; a++) coorArr[a] = tmp[a];
	free(tmp);	//메모리 해제
}
void mergeSort(int p, int r) {
	int q;
	if (p < r) {
		q = (p + r) / 2;
		mergeSort(p, q);
		mergeSort(q + 1, r);
		merge(p, q, r);
	}
}
//배열 출력
void printArr() {
	for (int i = 0; i < n; i++) printf("%d %d\n", coorArr[i].x, coorArr[i].y);
}
int main(void) {
	scanf("%d", &n);
	coorArr = (coor*)malloc(sizeof(coor) * n);
	for (int i = 0; i < n; i++) scanf("%d %d", &coorArr[i].x, &coorArr[i].y);
	mergeSort(0, n - 1);
	printArr();
	return 0;
}