정렬 후 사용자의 나이와 이름을 뽑아주세요.
stl sort를 사용하여 입력 끝난 후 sort한번 후 뽑아냈다.
sorting 하는 방법이 크게 2개 있다.
1. priority queue를 사용하여 입력때마다 소팅의 비용을 내는 방법과
2. 입력을 끝까지 다 받아놓은 다음 한번에 소팅의 비용을 내는 방법이 있다.
두 방법 다 asymtotic하게 O(n logn)이다.
데이터가 들어오는 순서에 따라 1번이 유리할 수도 2번이 유리할 수도 있다.
정렬된 데이터가 들어왔을 때 insertion sort가 worst case O(n^2)이어도 가장 빠른 것처럼..
https://stackoverflow.com/questions/3759112/whats-faster-inserting-into-a-priority-queue-or-sorting-retrospectively/10761286
cpp의 cout이 endl을 썼을 때 상당히 느려진다.'\n'으로 교체 해줬다.
cpp stl sort가 stable sort인줄알고 입력 순서에 대해 custom compare 함수에 명시하지 않았다.
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
struct person {
int age, idx;
string name;
};
//cpp는 sorting이 stable하지 않다는 걸 깨달았다!
bool comp(person &a, person &b) {
if (a.age == b.age) return a.idx < b.idx;
return a.age < b.age;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<person> v;
int age;
string name;
for (int i = 0; i < n; i++) {
cin >> age >> name;
v.push_back(person{ age, i, name });
}
sort(v.begin(), v.end(), comp);
for (int i = 0; i < v.size(); i++) {
cout << v[i].age << " " << v[i].name << '\n';
}
}