[백준 - 11650] 좌표 정렬하기 - C++

분류: 정렬, 좌표정렬 /

 

문제

문제 링크

문제 설명

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

입력

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

출력

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

 

풀이

- STL sort + cmp

#include <iostream>
#include <algorithm>
using namespace std;

struct xy {int x, y;};
bool cmp(const xy &a, const xy &b) { 
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
xy points[100000];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> points[i].x >> points[i].y;
    sort(points, points + N, cmp);
    for(int i=0; i<N; i++) cout << points[i].x << ' '<< points[i].y << '\n';
}

- Merge Sort

#include <iostream>
using namespace std;

struct xy {int x, y;};
bool cmp(const xy &a, const xy &b) { 
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
xy points[100000], tmp[100000];

void mergeSort(int start, int end) {
    if(end - start <= 1) return;
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid, end);
    int left = start, right = mid;
    for(int i = start; i < end; i++) {
        if(left == mid) tmp[i] = points[right++];
        else if(right == end) tmp[i] = points[left++];
        else if(cmp(points[left], points[right])) tmp[i] = points[left++];
        else tmp[i] = points[right++];
    }
    for(int i = start; i < end; i++) points[i] = tmp[i];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> points[i].x >> points[i].y;
    mergeSort(0, N);
    for(int i=0; i<N; i++) cout << points[i].x << ' '<< points[i].y << '\n';
}