백준 11651번 : 좌표 정렬하기 2

2019-07-03

BOJ

문제설명

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

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

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

접근

C++의 강점인 STL 중에 pair를 쓰는 문제이다. 두 정수가 한 쌍으로 주어지고, 그 쌍의 한 요소를 기준삼아 정렬해야 하기 때문이다. 사실 pair로 vector를 만든 후에 첫번째 요소로 정렬하는 것은 이미 구현되어있다. 하지만 문제에서 요구하는 “두번째 요소로 정렬, 그리고 두번째 요소가 같을 경우엔 첫번째로 정렬”을 구현하기 위해서는 sort 함수를 조금 고쳐야 한다. (이 때, 내장되어있는 sort함수의 세번째 인자가 어떻게 구성되어있는지 알 필요가 있다.)

코드

#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>

using namespace std;

bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) {
    if (a.second == b.second) return (a.first < b.first);
    return (a.second < b.second);
}

int main() {
    int N, i, j, k;
    vector< pair<int, int> > v;

    scanf("%d ", &N);

    for(i = 0; i < N; i++) {
        scanf("%d %d", &j, &k);
        v.push_back(pair<int, int>(j, k));
    }
    sort(v.begin(), v.end(), sortbysec);

    for(i = 0; i < N; i++) {
        printf("%d %d\n", v[i].first, v[i].second);
    }

    return 0;
}