백준 10814 나이순 정렬 - c++

벡터를 가지고 sorting만 할 줄 알면 푸는 문제이다.

필자는 'paired vector'일 경우에는, 어차피 first를 가지고 정렬하기 때문에 다른 것 필요없이 sort함수를 그냥 갖다 쓰면 될줄 알았는데 그렇게 하니까 결과값이 이상하게 나온걸 깨달았음..

 

1. sort를 쓰면 안되고 stable sort를 사용해야 한다.

std::sort는 두 원소가 같을 때 기존의 순서를 유지해준다는 보장이 없는 unstable sort이다. 이 때문에 "나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다."가 지켜지지 않는다.

 

2. cmp 함수를 따로 만들어야 하는 필요성

pair::operator 자체가 first가 같으면 그 다음 second를 비교하기 때문에 {21,jun}과 {21,do}는 대소관계가 성립하는 서로 다른 값이다. 따라서 stable이든 아니든 같은 결과를 내게 된다.

pair에서 stable_sort를 통해 순서가 유지되려면 second까지 같아야 한다.. 

 

 

따라서 cmp라는 bool type 함수를 만들어서 해결.

first만 보고 second는 아예 안보게 해결하면 풀 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<pair<int,string>> v;
bool cmp (pair<int, string> u, pair<int, string> v)
{
    return u.first < v.first;
}
 
int main(void){
    int n,age;
    string name;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>age>>name;
        v.push_back(make_pair(age,name));
 
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0; i<n; i++){
        cout<<v[i].first<<" "<<v[i].second<<"\n";
    }
}