[ C++/cpp ] 백준 (10814 나이순 정렬) ⭐sort_stable

백준 10814번 나이순 정렬

(실버 5)

 

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

 

 

(정답 코드)

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

using namespace std;
typedef pair<int,string> p;

bool cmp(const p &a, const p &b) {
    
    // 나이순 정렬
    if(a.first!=b.first) {
        return a.first < b.first; 
    } 
    
    // 나이가 같으면 변화없이 그대로 !
    else {
        return false; // 원래 순서 유지 !
    }
}


void sortUser(vector<p>& user) {
    
    // 입력 순서를 보존하는 안정적인 정렬을 보장하는 sort_stable
    stable_sort(user.begin(), user.end(), cmp); 
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 입력
    int n;
    cin >> n;
    
    int age;
    string name;
    
    vector <p> user;
    
    while (n--) {
        cin >> age >> name;
        user.push_back(make_pair(age, name));
    }
    
    // 연산
    sortUser(user);
    
    
    // 출력
    for (int i=0; i<user.size(); i++) {
        cout << user[i].first << " " << user[i].second << '\n';
    }

    return 0;
}

 

 

나이가 같은 경우엔, 먼저 가입한, 즉 먼저 입력된 순서로 출력해야한다. 그런데 이 부분에서 오류가 있었다.

비교함수의 리턴값을 false로 하면, 정렬없이 원래 순서가 유지된다고 해서

입력 순서 그대로 변화가 없을 것으로 예상해 그렇게 비교함수를 작성해서 풀었는데 틀렸다..

 

질문게시판을 보니 sort_stable로 풀어야 맞다길래 그 부분만 수정하니 맞음 ...! 왜 인지 궁금해서 더 찾아보았다.

 

🔎 sort와 sort_stable의 차이

 

사실, std::sort 함수는 안정적인 정렬을 보장하지 않습니다. 따라서 같은 값에 대해 입력 순서를 유지하지 않을 수 있습니다. 그러나 C++11 이후로 std::sort 함수는 안정 정렬을 수행하는데, 이는 특정 구현에 따라 달라질 수 있습니다.

 

반면 std::stable_sort 함수는 항상 안정적인 정렬을 보장합니다. 이는 입력 순서를 보존하는 것을 의미합니다. 그러나 안정적인 정렬을 유지하면서도 일반적인 std::sort보다 성능면에서는 조금 더 느릴 수 있습니다.

 

따라서 입력 순서를 유지하면서 정렬을 수행하려면 std::stable_sort 함수를 사용해야 합니다. 이를 이용하여 코드를 수정하고 다시 제출하면 올바르게 작동할 것입니다.

 

 

챗 지피티 체고 :)..