[C언어] 백준 11650 : 좌표 정렬하기

생각의 흐름

1. 아 쉬워보인다 그냥 x[i]랑 y[i]를 같이 정렬해버리면 되겠네 선택정렬 해야겠다
2. 만약에 안되면 뭐 퀵정렬 고민해봐야지

내가 처음에 푼 코드(시간 초과)

#include <stdio.h>

int main()
{
    int n,i,j;
    scanf("%d", &n);
    int x[n], y[n];
    i = 0;
    while(i < n)
    {
        scanf("%d %d", &x[i], &y[i]);
        i++;
    }
    i = 0;
    while(i < n - 1)
    {
        j = i + 1;
        while(j < n)
        {
            if(x[i] >= x[j] && y[i] >= y[j])
            {
                int temp;
                temp = x[i];
                x[i] = x[j];
                x[j] = temp;
                temp = y[i];
                y[i] = y[j];
                y[j] = temp;
            }
            j++;
        }
        i++;
    }
    i = 0;
    while(i < n)
    {
        printf("%d %d\n",x[i], y[i]);
        i++;
    }
}

생각의 흐름

시간초과가 났다. 퀵정렬을 사용하려고 고민했다. 근데 문제가 생겼다.
1. 퀵 정렬을 직접 구현하는건 내 현재 실력으론 부족하다. 그러면 내장함수를 사용해야되는데, qsort에는 1개의 배열밖에 안들어가고, compare또한 2개의 값을 비교해줄 뿐이다.
2. 하지만 우리가 원하는 건 x좌표뿐만 아니라 y좌표까지 고려를 해주어야 한다. compare에 if x == x1 일 경우에, y좌표를 고려할 방법이 생각이 안났다.
3. 결국 구글링을 한 뒤 구조체를 사용하는 방법이 있다는걸 찾았다.

• 구조체를 사용함으로써 위 문제들을 다 해결해버렸다.

수정 후

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int x;
    int y;
} coord; //coord형의 구조체 선언

int compare(const void *a, const void *b)
{
    coord A = *(coord *)a; //coord형의 A로 입력받은 a를 사용할 수 있게한다.
    coord B = *(coord *)b;
    if (A.x > B.x) // 구조체의 x를 끌고와서 사용한다. 오름차순 정렬
        return 1;
    else if (A.x == B.x) // x좌표가 같다면,
    {
        if (A.y > B.y) // y좌표를 비교한다. 오름차순 정렬
            return 1;
        else
            return -1; // 그게 아니라면 -1반환.
    }
    return -1; // A.x < B.x면 -1
}

int main()
{
    int n, i;
    scanf("%d", &n);
    i = 0;
    coord arr[n]; // 구조체형으로 배열을 선언한다.
    while (i < n)
    {
        scanf("%d %d", &arr[i].x, &arr[i].y);
        // 구조체배열로 arr[0]의 x값,y값 각각 설정하면서 간다.
        i++;
    }
    qsort(arr, n, sizeof(coord), compare); // 퀵정렬 사용
    i = 0;
    while (i < n)
    {
        printf("%d %d\n", arr[i].x, arr[i].y); // 정렬된 배열 출력
        i++;
    }
}

이번에 진짜 엄청나게 많이 배웠다. 구조체라는걸 알고만 있었지, 왜 사용하는지, typedef를 왜 사용하는지, 그냥 등등 굉장히 뿌듯하다.
https://dojang.io/mod/page/view.php?id=409 typedef 사용하는 이유

https://sedangdang.tistory.com/16 코드 참고 사이트
https://velog.io/@inwooleeme/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-11650%EB%B2%88-%EC%A2%8C%ED%91%9C-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0 코드 참고 사이트2 <- 이분한테 많이 배웠다.

https://modoocode.com/55 구조체의 개념 정리.