10814 나이순 정렬

나이가 같다면 먼저 가입한 사람이 앞에 오는 순서?

 

이거 전에 했었는데 그 정렬할 때 stable하게 하는거.. 생각하면서 이전 문제 찾다가 그 때 풀었던 문제랑 동일한 문제라는 걸 깨달았다ㅋㅋㅋㅋ

 

stable_sort()를 쓰면 됩니다.

 

시간복잡도가 느리다는 기억이 있어서 찾아보니 sort는 quick sort로 내부구현이 되어있고 stable_sort()는 merge sort로 내부 구현이 되어있다고 한다. 그러므로 nlogn이 걸림

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

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

int     main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<pair<int, string>> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].xx >> v[i].yy;

    stable_sort(all(v), sortbyfirst);
    for (int i = 0; i < n; i++)
        cout << v[i].xx << " " << v[i].yy << '\n';

    return 0;
}

 

처음에 코딩할 때 시간초과나서 찾아보니 cin.tie(NULL) 체크를 안 했다

 

하니깐 통과했음