[알고리즘] 백준 11650 - 좌표 정렬하기

실버 5 🪴
https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

문제 설명

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

제한 조건

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

입출력 예

 

 

 

---

해결방법

x 좌표와 y 좌표를 가지는 pair 를 만들어서 정렬해준다. 좌표문제를 풀 때 기초가 되는 내용이다.

Pair 클래스를 이용하면 두 객체를 하나의 객체로 취급하도록 묶어준다. 보통 쌍을 표현할때 사용한다. make_pair() 함수를 이용해서 pair를 만들고 compare 을 정의해서 정렬할 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b)
{
    int ax = a.first;
    int ay = a.second;
    int bx = b.first;
    int by = b.second;
    if (ax == bx)
        return ay < by;
    return ax < bx;
}

int main(void) {
    int n, x, y;
    vector<pair<int, int>> v;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        v.push_back(make_pair(x, y));
    }
    sort(v.begin(), v.end(), compare);
    for (auto p: v)
        cout << p.first << ' ' << p.second << "\n";
    return 0;
}