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

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

bool compare(pair<int, string> a, pair<int, string> b){
    return a.first < b.first; // 나이만 비교한다.
}

int main(int argc, char **argv){ // 시간초과, 원래 순서 손상 안시키게 정렬하는것 stable sort
    int N;
    string str;
    scanf("%d",&N);
    vector<pair<int, string> > arr;
    pair<int, string> tmp;

    for(int i=0; i<N; i++){
        cin >> tmp.first >> tmp.second;
        arr.push_back(tmp);
    }

    stable_sort(arr.begin(), arr.end(), compare); // stable_sort 사용시 컨테이너 앞의 원소 순서대로 정렬

    for(int i=0; i<arr.size(); i++){
        cout << arr[i].first << " " << arr[i].second << "\n";
    }

    return 0;
}

오늘의 키포인트

• 다시 풀어봐야 할 문제.

• STL stable_sort를 사용한다. 일반 sort 사용시, compare 함수(pair의 first가 작다면 앞에 오도록)를 사용한다면 42, 44 이렇게 두 수가 왔을때 무엇이 먼저올지는 불확실하다. 랜덤이다. (퀵소트)
  하지만 stable_sort를 사용하였기 때문에 컨테이너의 앞의 원소 순서대로 정렬이 된다. 그러므로 42, 44가 온다면 그대로 42, 44 이렇게 정렬이 된다.