(10814) 나이순 정렬

https://www.acmicpc.net/problem/10814

단계별로 풀어보기

13단계(정렬) 10번째

 

 

 

C++의 sort함수는 퀵 정렬을 기반으로 하기 때문에 속도가 빠르지만 불안정 정렬이다. 안정 정렬이 필요할 땐 병합 정렬을 기반으로 한 stable_sort함수를 사용하면 된다.

둘 다 시간복잡도는 O(n log n)이지만 stable_sort가 순서 보존을 위한 연산이 조금 더 필요해 조금 더 느린데, 일반적인 PS 수준에선 크게 신경쓰지 않아도 될 정도라고 생각한다.

또한 C++14부터 람다 함수 내 auto 키워드를 사용할 수 있으므로 비교 함수를 작성할 때 이런 복잡한 자료형을 다시 쓸 필요 없이 간단하게 auto로 표현할 수 있다.

 

마지막으로 이 문제에서 적용되는 이야기지만, 데이터를 pair 클래스로 저장했다면 pair 클래스의 기본 비교 함수는 앞쪽 원소부터 순차적으로 비교하므로 그대로 정렬해버리면 나이가 같을 때 이름을 사전 순서로 정렬해버리니 주의해야 한다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<pair<int,string>> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i].first >> v[i].second;
  
  stable_sort(v.begin(), v.end(), [](auto A, auto B){
    return A.first<B.first;
  });
  
  for(auto elem:v)  cout << elem.first << " " << elem.second << "\n";
  
  return 0;
}