[11651] 좌표 정렬하기 2(C)

문제

[11651] 좌표 정렬하기 2

 

bubblesort를 사용했을 때 런타임에러가 발생하여

복잡도가 가장 낮은 quicksort를 사용하였는데도

계속 실행이 안되거나 틀렸습니다... 시간초과..컴파일에러..런타임에러가 종합해서 계속 나타났다....^^

 

나머지 두 문제는 너무 쉬워서 수요일에 다 끝내버렸는데 이 문제 때문에 과제 제출하지도 못하고 4일동안을 끙끙대고 있었다.

그냥 unsolved에 올리고 다른거 할까도 계속 생각했지만

거의 다 된 것 같은데 어디서 실수하고 있다는 생각이 자꾸만 들어서 계속 붙잡고 있었던 것 같다.

그리고 결국 성공했다!

구글링했을 때 c언어로 푼 코드가 단 하나도 없어서 때려치고 싶었는데

그래도 뿌듯하다ㅎㅎ

 

 

내 코드(C)

// [11651] 좌표 정렬하기2
#include <stdio.h>
#define MAX 100000

typedef struct twodimen {
    int x;
    int y;
}twod;

void swap(twod arr[], int a, int b);
int partition(twod arr[], int left, int right);
void quicksort(twod arr[], int left, int right);

int main(void)
{
    int n; // 점의 개수
    twod dot[MAX];
    scanf_s("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf_s("%d %d", &dot[i].x, &dot[i].y);
    }

    quicksort(dot, 0, n - 1);

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

void swap(twod arr[], int a, int b)
{
    twod temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

int partition(twod arr[], int left, int right)
{
    int pivot = left;
    int low = left + 1;
    int high = right;

    // 교차되기 전까지 반복
    while (low <= high) {

        // pivot보다 큰 값을 찾는 과정
        while (arr[pivot].y >= arr[low].y) {
            if (arr[pivot].y == arr[low].y) {
                if (arr[pivot].x > arr[low].x)
                    low++;
                else
                    break; // ★핵심!★
            }
            else
                low++;
        }

        // pivot보다 작은 값을 찾는 과정 
        while (arr[pivot].y <= arr[high].y) {
            if (arr[pivot].y == arr[high].y) {
                if (arr[pivot].x < arr[high].x)
                    high--;
                else
                    break; // ★핵심!!★
            }
            else
                high--;
        }

        if (low <= high) // 교차되지 않은 상태이면 swap
            swap(arr, low, high); 
    }

    swap(arr, left, high); // pivot과 high교환
    return high; // 옮겨진 pivot의 위치정보 반환
}

void quicksort(twod arr[], int left, int right)
{
    if (left <= right) {
        int pivot = partition(arr, left, right); 
        quicksort(arr, left, pivot - 1); // 왼쪽 정렬
        quicksort(arr, pivot + 1, right); // 오른쪽 정렬
    }
}