11650번 좌표 정렬하기

※ C언어로 구현

알고리즘 순서

① x, y를 구조체로 생성한다.

② x를 기준으로 먼저 오름차순으로 퀵 정렬을 한다.

③ 같은 x일 경우에만, y를 오름차순 퀵 정렬을 한다.

이 문제에서는 좌표가 중복을 허락하므로, 

31, 37, 74, 80번 째 while문 안에 map과 pivot의 x, y좌표를 비교할 때, '='가 붙는다.

133 ~ 134번 째 주석도 참고하자.

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

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
 
typedef struct Map
{
    int x;
    int y;
}Map;
 
Map map[100001];
 
int N = 0;
 
void Swap(int a, int b)
{
    Map temp = map[a];
    map[a] = map[b];
    map[b] = temp;
}
 
int partitionX(int start, int end)
{
    Map pivot = map[end]; // pivot 인덱스 = end
    int left = start;
    int right = end;
 
    while (left < right)
    {
        while (map[left].x <= pivot.x && left < right)
        {
            // pivot 보다 큰 값을 찾을 때 까지, 이동
            ++left;
        }
 
        while (map[right].x >= pivot.x && left < right)
        {
            // pivot 보다 작은 값을 찾을 때 까지, 이동
            --right;
        }
 
        if (left < right)
        {
            Swap(left, right);
        }
    }
 
    Swap(right, end);
 
    return right;
}
 
void quickSortX(int start, int end)
{
    int pivot = 0;
 
    if (start < end)
    {
        pivot = partitionX(start, end);
        quickSortX(start, pivot - 1);
        quickSortX(pivot + 1, end);
    }
}
 
int partitionY(int start, int end)
{
    Map pivot = map[end]; // pivot 인덱스 = end
    int left = start;
    int right = end;
 
    while (left < right)
    {
        while (map[left].y <= pivot.y && left < right)
        {
            // pivot 보다 큰 값을 찾을 때 까지, 이동
            ++left;
        }
 
        while (map[right].y >= pivot.y && left < right)
        {
            // pivot 보다 작은 값을 찾을 때 까지, 이동
            --right;
        }
 
        if (left < right)
        {
            Swap(left, right);
        }
    }
 
    Swap(right, end);
 
    return right;
}
 
void quickSortY(int start, int end)
{
    int pivot = 0;
 
    if (start < end)
    {
        pivot = partitionY(start, end);
        quickSortY(start, pivot - 1);
        quickSortY(pivot + 1, end);
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d", &map[i].x, &map[i].y);
    }
 
    quickSortX(0, N - 1);
 
    int start = 0;
    int end = N - 1;
    int cnt = 0;
 
    for (int i = 0; i < N - 1; i++)
    {
        while (map[i].x == map[i + 1].x)
        {
            end = i + 1;
            ++cnt;
            ++i;
        }
 
        // 위에서 while을 탈출 할 때, i는 어차피 다른 숫자가 나오기 전의 인덱스에 머문다.
        // 즉, 그래서 for문의 i++에 의해서 다시 다른 숫자부터 바로 시작할 수 있다.
        
        if (cnt >= 1)
        {        
            start = end - cnt;
            quickSortY(start, end);
        }
 
        cnt = 0;
    }
 
    for (int i = 0; i < N; i++)
    {
        printf("%d %d\n", map[i].x, map[i].y);
    }
 
    return 0;
}