백준11650번: 좌표 정렬하기 (퀵정렬구현)

시간 제한         메모리 제한                      제출                              정답                         맞힌 사람                  정답 비율

1 초

256 MB

128117

61154

47487

47.922%

문제

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

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

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

---

내가 작성한 코드:

#include <stdio.h>

void quickSort(int x[], int y[], int left, int right) {

if (left >= right) return;

int pivotX = x[(left + right) / 2];

int pivotY = y[(left + right) / 2];

int i = left, j = right;

while (i <= j) {

while (x[i] < pivotX || (x[i] == pivotX && y[i] < pivotY)) i++;

while (x[j] > pivotX || (x[j] == pivotX && y[j] > pivotY)) j--;

if (i <= j) {

int temp = x[i];

x[i] = x[j];

x[j] = temp;

temp = y[i];

y[i] = y[j];

y[j] = temp;

i++;

j--;

}

}

quickSort(x, y, left, j);

quickSort(x, y, i, right);

}

int main() {

int x[100000], y[100000], m;

scanf("%d", &m);

for (int i = 0; i < m; i++) {

scanf("%d %d", &x[i], &y[i]);

}

quickSort(x, y, 0, m - 1);

for (int i = 0; i < m; i++) {

printf("%d %d\n", x[i], y[i]);

}

return 0;

}

위 문제는 시간제한으로 인해 시간복잡도가 O(n) = n^2인 버블, 삽입정렬보다 빠른 정렬방식을 사용해야한다.

나는 퀵정렬을 선택하였다. 앞선 문제에선 퀵정렬함수를 사용할 수 있었지만,

위 문제의 경우 x가 겹칠경우 y값을 비교해야하기 때문에 함수를 직접 구현해줬다.

기본적인 원리는 퀵정렬함수와 같지만 x가 겹치는 경우, y값을 비교하여 교환하는 값의 인덱스를 정해주었다.

---

6일만에 돌아왔다.

퀵정렬의 늪에서 헤어나오지 못해 몇시간을 잡고 있었는지 모르겠다.

재귀함수는 언제나 내 머리를 터트린다. 

정의나 방식은 어렵지 않지만 이를 구현하고 응용하는것은 다른 차원의 문제이다..

오늘부터 다시 힘내보도록 하겠다..