[백준/C++] 10814 나이순 정렬 - (1)

백준 10814번 나이순 정렬 

 

이 문제는 시간 초과를 염두해야해서 이중 for문은 불가하다.

그러면 sort함수를 사용하여 시간복잡도가 O(nlogn)으로 내려가게 만들어줘야한다.

 

하지만, 여기서 문제의 조건 중 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 만들어야한다. 따라서, 순서를 기억하는 방법과 stable_sort를 사용하는 방법이 있다. 

 

bool compare(pair<int, string> a, pair<int, string> b)
{
    return a.first < b.first;
}

stable_sort(arr.begin(), arr.end(), compare);

 

stable _sort의 사용 방법은 위 처럼 vector의 시작점과 끝점을 넣어주고 조건을 달아주면 끝이다.

compare 조건문 안에서 a가 b보다 작으면 True, 크면 false를 해주면 된다. 

 

이 함수는 stable_sort 함수가 벡터를 정렬할 때 각 pair<int, string>의 첫 번째 요소(int)를 기준으로 오름차순으로 정렬하는 역할을 한다.

 

---

10814번 전체 코드 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, string> a, pair<int, string> b)
{
    return a.first < b.first;
}
int main() {
    int num;
    cin >> num;
    pair<int, string> tmp;
    vector<pair<int, string>> arr;
    for (int i = 0; i < num; i++)
    {
        cin >> tmp.first >> tmp.second;
        arr.push_back(tmp);
    }
    stable_sort(arr.begin(), arr.end(), compare);
    for (int i = 0; i < num; i++)
        cout << arr[i].first << ' ' << arr[i].second << '\n';
}