백준 11650번: 좌표 정렬하기 - c언어

Yeonsu Summer·2022년 9월 1일

목록 보기

14/24

문제

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

입력

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

출력

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

예시

입력 출력
5
3 4
1 1
1 -1
2 2
3 3 1 -1
1 1
2 2
3 3
3 4

입력	출력
5 3 4 1 1 1 -1 2 2 3 3	1 -1 1 1 2 2 3 3 3 4

나의 생각

#include <stdio.h>

int main() {
    int N, x[100000] = {0, }, y[100000] = {0, }, temp;
    
    scanf("%d", &N);
    
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &x[i], &y[i]);
        
        for (int j = 0; j < i; j++) {
            if (x[i] > x[j] || y[i] > y[j]) {
                temp = x[i];
                x[i] = x[j];
                x[j] = x[i];
                
                temp = y[i];
                y[i] = y[j];
                y[j] = y[i];
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        printf("%d %d", x[i], y[i]);
    }
    
    return 0;
}

이 코드로 제대로 출력이 됐을지 모르겠지만, 시간초과로 이미 오답인 상태이다.

for문을 쓰지 않으면 어떻게 풀까?

구글링을 해본 결과 퀵정렬을 사용하는 방법이 있었다.
자료구조 시간에 공부를 했지만 직접 코드를 짜본 적이 없어서 굉장히 당황스러웠다...

제출한 답

#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 B = *(coord *)b;
    
    if (A.x > B.x) {
        return 1;
    }
    else if (A.x == B.x) {
        if (A.y > B.y)
            return 1;
        else
            return -1;
    }
   
    return -1;
}

int main()
{
    int n;
    
    scanf("%d", &n);
    
    coord arr[n];
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &arr[i].x, &arr[i].y);
    }
    
    qsort(arr, n, sizeof(coord), compare);
    
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", arr[i].x, arr[i].y);
    }
    
    return 0;
}

퀵 정렬 라이브러리 함수를 사용하였다.

함수의 원형

void qsort(
	void *base,  // 배열의 시작주소
    size_t num,  // 배열 요소의 개수
    size_t width,  // 배열 요소 하나의 크기 (byte 단위)
    int (*compare)(const void *, const void *)  // 포인터를 통하여 두 개의 요소를 비교해 결과를 정수로 반환하는 함수
);