#10814 나이순정렬 (c++)

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

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

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    vector <pair <int,string>> v;
    cin >> T;

    for(int i=0; i<T; i++){
        int age = 0; string name;
        cin >> age >> name;
        v.push_back(pair<int,string>(age,name));}
    
    stable_sort(v.begin(),v.end(),check);
    
    for(int i=0; i<T; i++)
        cout << v[i].first << " " << v[i].second << "\n";
    
    return 0;
}

단 번에 맞을 거라는 예상과 달리, 의외로 시행착오를 겪었던 문제. 

반례를 찾아가며 다양한 테스트 케이스를 돌리다가 어떤 부분이 틀린건지 알게되었다. 

 

1. Stable_sort() VS sort()

(참고 : https://blog.naver.com/chogahui05/221215669388)

안정 정렬 (stable sort)이란 뭘까요?

단순 sort로 정렬을 진행 할 경우, 우선순위가 동등할 때 '들어온 순서'에 따른 기존의 순서는 필수적으로 지켜지지 않는다. 

10개 정도의 입력 값에서는 정답이 나올 수 있으나, 많은 데이터가 입력 될 경우 순서가 지켜지지 않을 수 있다고 한다. 

때문에 들어온 순서또한 안정적이게 지켜질 수 있도록, 두 가지 방법 중 하나를 선택해서 풀어야한다. 

(1) 별도로 순서를 지켜내는 조건 삽입   (2) stable_sort를 사용하여 우선순위가 동등할 때 기존의 순서 유지 

 

2. 나이가 같은 경우의 조건문

bool check(pair<int,string>a, pair<int,string>b){
    if(a.first==b.first) return a==b;
    else return a.first<b.first;
}

...

stable_sort(v.begin(),v.end(),check); 
// 혹은
sort(v.begin(),v.end(),check);

모든 테스트케이스는 성공하였으나, 채점시 4%에서 틀렸다고 나온 소스. 

 

(1) sort를 사용한 경우

1번의 내용을 참고. 

사실 sort 문제가 아니라 하단의 (2)의 문제가 원인이다. 

 

(2) stable_sort가 틀린 경우

사실 위 코드는 근본적으로 if(a.first==b.first)에서 틀려다. 

생각해보자. 두 vector에서 int값(나이)가 같을 경우, 두 vector a와 b가 같아야지 true를 return한다.

이름이 같지 않을 경우 결국 false를 return하고, 그럼 기본 sort의 default인 '<' 연산자가 적용되어 

나이가 같은 pair라 하더라도 'a<a'라는 완전히 잘못된 정렬이 나오게 된다. 

백준G****55님의 Feedback