[백준] 10814 나이순 정렬

문제 요약

• 사용자 정보 : 나이, 이름
• 정렬 우선 순위 : 나이->입력 순서

정렬 후 사용자의 나이와 이름을 뽑아주세요.

아이디어

stl sort를 사용하여 입력 끝난 후 sort한번 후 뽑아냈다.

그냥 궁금해서.. sort : pq vs sort which one is faster?

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';
	}
}