[알고리즘] 백준 11650번 "좌표 정렬하기" (C/C++) - Don 임베디드

문제 요약:

 

2차원 평면 위에 점 N개의 좌표가 주어진다.

N개의 좌표들을 X 좌표가 증가하는 순으로,

X 좌표가 같으면 Y 좌표가 증가하는 순으로 정렬한 뒤 출력하는 프로그램을 작성하라.

 

첫 줄에는 입력될 좌표의 개수 N이 주어진다.

둘째줄 부터 N개의 줄에는 i번 점 (Xi, Yi)가 주어진다.

좌표는 항상 정수이고, 위치가 완전히 동일한 좌표는 주어지지 않는다.

 

 

제약:

 

제한시간 1초, 메모리 제한 256MB

1 <= N <= 100000

좌표 Xi, Yi는 정수.

-100000<= Xi, Yi <= 100000

 

 

예제:

예제 1 입력.	예제 1 출력.
5 3 4 1 1 1 -1 2 2 3 3	1 -1 1 1 2 2 3 3 3 4

정답 코드:

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
 
 
bool compare(pair<int, int> &A, pair<int, int> &B)
{
    // x내림차순, x좌표가 같으면 y 내림차순으로 정렬하기 위한
    // custom compare 함수.
    if (A.first < B.first)
    {
        return true;
    }
    else if (A.first == B.first)
    {
        return (A.second < B.second);
    }
    else
    {
        return false;
    }
}
 
int main()
{
    int N, nTmpX, nTmpY;
    vector <pair<int, int>> v;        // <int , int> pair의 벡터 v 생성.
    
    // 입력 받을 좌표의 개수.
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        // vector v에 입력 받은 N개의 좌표를 차례대로 push.
        cin >> nTmpX >> nTmpY;
        v.push_back(pair<int, int>(nTmpX, nTmpY));    
    }
 
    // x내림차순, x좌표가 같으면 y 내림차순으로 정렬
    sort(v.begin(), v.end(), compare);
 
    for (int i = 0; i < N; i++)
    {
        // 정렬된 N개의 좌표 출력.
        // endl 사용시 출력 시간때문에 Time Out발생!!!!!
        // cout << v.at(i).first << " " << v.at(i).second << endl;
        cout << v.at(i).first << " " << v.at(i).second<< '\n';
 
    }
    return 0;
}

원본 링크: https://www.acmicpc.net/problem/11650