백준, BOJ, 10814번 C++ [CPP]

//2022.04.07 다시 업데이트

 

음 나는 조금 어렵게 생각했나보다..

남들은 쉽게 풀더라.

 

 

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

 

---

 

우선 내 풀이는 이렇다.

# 맞은 풀이

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

using namespace std;

struct Id{
    int order;
    int age;
    string name;
};

//const와 &을 받아옴

bool comp(const Id &p1, const Id &p2){
    if(p1.age< p2.age){
        return true;
    }
    else if(p1.age == p2.age){
        return p1.order < p2.order;
    }else{
        return false;
    }
}

int N;

vector<Id> v;
int main(){
    cin >> N;
    for(int i = 1; i<=N; i++){
        Id n;
        cin >> n.age >> n.name;
        n.order = i;
        v.push_back(n);
    }
    
    sort(v.begin(),v.end(), comp); // 나이순 정렬 -> 가입순 comp로 비교
    
    for(auto c : v){
        cout << c.age << " " << c.name << "\n";
    }
}

 

 

근데 여기서 안정 정렬, stable sort()라는 것을 알려줘서 해봤다.

 

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

using namespace std;


bool comp(pair<int, string> x, pair<int, string> y)
{
    return x.first < y.first;
}

int N;

vector<pair<int, string>> v;

int main(){
    cin >> N;
    for(int i = 1; i<=N; i++){
        int a;
        string b;
        cin >> a >> b;
        v.push_back({a,b});
    }
    
    stable_sort(v.begin(),v.end(),comp); // 나이순 정렬 (가입순 x)
    
    for(auto c : v){
        cout << c.first<< " " << c.second << "\n";
    }
}

 

음...

comp만드는 것까지는 똑같다.

그냥 comp에서 조건을 더 넣느냐 아니냐? 이 정도 차이다.

 

내가 만든 comp함수도 안정 정렬이라고 볼 수 있겠다.

입력받은 순서를 index로 받아서 index를 비교하니까..?

 

뭐 굳이 안정정렬이란 것을 알 필요는 없어보인다.

내가 만들면 되니까..?

 

//////////////////////////////////////////////////////////

 

다시 풀어보면서 느꼈다.

안정 정렬이란 것을 알 필요는 있다.

정렬함에도 순서가 입력 순서대로 유지된다는 것이 필요하긴 하다.