[백준][C++] 10814: 나이순 정렬

문제 링크: https://www.acmicpc.net/problem/10814

 

회원들을 나이 오름차순으로 정렬하는 것이 목표입니다. 나이가 같으면 먼저 가입한 사람이 앞에 오는 순으로 정렬하는데, 정렬할 때 미리 인덱스를 저장해놔서 인덱스를 비교하거나, 아니면 stable sort를 사용하면 되겠습니다.

std::sort는 unstable sort이기 때문에 std::stable_sort 또는 stable한 정렬방법을 사용해야 합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	vector<pair<int, string>> persons(n);
	for (auto& [age, name] : persons) {
		cin >> age >> name;
	}

	stable_sort(persons.begin(), persons.end(), [](auto& p1, auto& p2) {
		return p1.first < p2.first;
	});

	for (auto& [age, name] : persons) {
		cout << age << ' ' << name << '\n';
	}

	return 0;
}

STL의 stable sort를 쓴 버전입니다. 메모리가 추가로 좀 들어갑니다.

 

std::stable_sort § Notes

This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted. If the allocation fails, the less efficient algorithm is chosen.

stable_sort의 레퍼런스 항목을 읽어보면 메모리 할당을 시도해보고, 메모리 할당이 되면 좀 더 효율적인 방법(O(NlogN))으로 정렬하고, 할당이 안되면 덜 효율적인 방법(O(Nlog(N^2)))이 사용된다네요.