[BOJ] 10814 나이순 정렬

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

10814번: 나이순 정렬

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

안정 정렬(stable sort)

 

---------------------------------------------------풀이----------------------------------------------------

 

algorithm의 기본 sort()함수를 사용하면 틀린다.

나이순 정렬인데, 나이가 같으면 입력된 순서대로 정렬해야 하므로 stable_sort()를 사용해야 한다.

insertion, merge, bubble sort를 사용하면 마찬가지의 결과를 얻을 수 있다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

// 나이가 증가하는 순으로 정렬
int main(void){
    FASTIO;
    int N;
    cin >> N;
    vector<pair<int,string> > v;
    for(int i = 0; i < N; i++){
        pair<int,string> p;
        cin >> p.first >> p.second;
        v.push_back(p);
    }
    stable_sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < v.size(); i++){
        cout << v[i].first << " " << v[i].second << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

처음에는 퀵소트를 사용하는 sort() 함수를 사용하거나 priority_queue를 사용해 틀린 결과를 얻었다.

아니면, 저장된 순서도 함께 저장해서 그에 맞춰 정렬하는 방법도 존재한다.