11650번 좌표정렬 BOJ 백준 C언어

문제

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

입력

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

출력

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

구현

두 개의 좌표를 받아서 순서대로 정렬하기 위해서는 2차원 배열을 사용하거나 구조체를 사용할 수 있다.

배열보다는 구조체가 x,y로 표현할 수 있어서 더 직관적이므로 구현 후 c++ 내장함수인 sort로 입력받은 좌표를 sorting 해준다.

소트 함수 사용 방법은 

std::sort(start,end,compare)

과 같은식으로 구현할 수 있다.

첫번째 인자로 시작값을 넣고 두번째 인자로 마지막값을 넣은 후 세번째 인자로 비교함수를 넣어준다.

비교함수의 경우 boolean 타입으로도 구현할 수 있는데

    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;

의 뜻은 a.x와 b.x의 값이 같을 경우에는 a.y가 먼저 출력되고 아닐 경우 a.x가 먼저 출력되도록 한다는 뜻이다.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define _CRT_SECURE_NO_WARNINGS

struct arr {
    int x;
    int y;
};

arr array[100000];

bool compare(arr const &a, arr const &b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int main(void) {
    int i = 0, num = 0, x, y;
    scanf("%d", &num);

    for (i = 0; i < num; i++) {
        scanf("%d", &x);
        scanf("%d", &y);
        array[i] = { x,y };
    }

    std::sort(array, array + num, compare);

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

정리

좌표정렬은 단순하게 STL라이브러리를 사용하지 않고도 쉽게 구현할 수 있다. 하지만 앞으로의 문제들이나 좀 더 나은 알고리즘의 구현을 위해서 내장 함수와 자료타입을 사용하는 것을 습관화 시켜야겠다.