[Baekjoon] 11650: 좌표 정렬하기 - (C2, S5) std::sort

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

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

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

11650번: 좌표 정렬하기

 

C++을 공부하면서 문제 풀기가 더 수월해졌다. C++은 C에 비해 라이브러리 함수가 많이 정의되어 있어 이 문제 역시 쉽게 풀 수 있었다. 

 

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

struct coordinate
{
    int x;
    int y;
};

int main()
{
    int N;
    cin >> N;

    coordinate pos[N];
    for (int i = 0; i < N; i++)
        cin >> pos[i].x >> pos[i].y;

    sort(pos, pos + N, [](const coordinate &a, const coordinate &b) {
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x; 
    });

    for (int i = 0; i < N; i++)
        cout << pos[i].x << " " << pos[i].y << "\n";

    return 0;
}

C++은 C와 달리 구조체 선언 시 typedef 선언을 생략해도 struct 키워드를 생략하고 구조체 변수를 선언할 수 있다. 

 

우선 N개의 좌표를 입력받아 구조체 배열에 저장한다. 그리고 sort함수를 이용하면 손쉽게 x 우선 정렬, y 기준 정렬을 수행할 수 있다. sort 함수는 다음과 같은 원형을 가진다. 

 

namespace std {
    template<class RandomIt>
    void sort(RandomIt first, RandomIt last);

    template<class RandomIt, class Compare>
    void sort(RandomIt first, RandomIt last, Compare comp);
}

 first와 last는 RandomIt 타입으로, 각각 정렬할 범위의 시작 반복자, 끝 다음 반복자이다. 쉽게 말해, first는 시작 주소, last는 끝 다음 주소이다. comp는 정렬의 기준이 되는 비교 함수로, 두 요소를 비교해 한 요소가 다른 요소보다 앞(true)이어야 하는지, 뒤(false)여야 하는지 비교한다. 기본값은 <로 오름차순 정렬된다. 

 

이 문제의 경우, 아래와 같이 람다 표현식을 사용하여 간단하게 정렬할 수 있었다. 

 

sort(pos, pos + N, [](const coordinate &a, const coordinate &b) {
	if(a.x == b.x)
    	return a.y < b.y;
	return a.x < b.x; 
});

 

C++로 문제를 풀 때 유의해야 할 사항은, std::endl은 버퍼를 비우고 개행하기 때문에 실행속도가 느리다. 따라서 std::endl 대신 escape sequence인 \n을 사용하여 개행을 하는 것이 좋다.