[C++] 백준 알고리즘 10814 나이순 정렬

10814번: 나이순 정렬 (acmicpc.net)

10814번: 나이순 정렬

두가지 값을 저장하는 것이므로 pair를 이용하면 된다.

단, 첫 번째 값인 나이순으로 정렬하되 두 번째 값인 이름은 입력 순서를 유지해야한다.

 

#include<algorithm> 안에 있는 sort 함수를 써서 정렬을 했다

계속 틀렸습니다가 떠서 당황했는데, 알아본 결과 sort의 경우 비교하는 값이 같을 경우에 원래 순서를 유지한다는 보장이 없다고 한다. 다시 말해 sort로 정렬하면 나이가 같은 사람들은 정렬 순서가 원래와 다르게 바뀔 수도 있다는 것이다.

 

stable_sort를 이용하면 정렬되지 않은 데이터는 원래 순서를 유지하며 정렬을 한다고 한다.

4%에서 '틀렸습니다'가 계속 나올 경우, sort가 아닌 stable_sort를 이용해보자

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

int main(){
    int n;
    cin>>n;
    vector<pair<int, string>> person(n);
    for(int i=0; i<n; i++)
        cin>>person[i].first>>person[i].second;

	//sort 함수 사용시 '틀렸습니다'
    stable_sort(person.begin(),person.end(),cmp);

    for(int i=0; i<n; i++)
        cout<<person[i].first<<' '<<person[i].second<<'\n';
}