백준 C++ 10814번 나이 순 정렬 문제 풀이

백준 C++ 10814번 나이 순 정렬 문제 풀이

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

 

풀이

bool compare(const pair<int, string> &cus1, const pair<int, string> &cus2){
    if(cus1.first == cus2.first){
        return false;
    }
    return cus1.first < cus2.first;
}

compare이라는 사용자 함수를 따로 정의하여 비교하는 코드를 짰다.

나이가 같을 경우에는 비교를 하지 않도록 나이가 다르다면 나이가 작은 사람이 먼저 오도록 코드를 구성하였다

만 나중에 이것이 필요하지 않았음을 깨닫게 됬다는.....

 

int main()
{
    int N;
    cin >> N;
    pair<int, string> customer [N];
    
    for(int i = 0; i < N; i++){
        cin>>customer[i].first>>customer[i].second;
    }
    
    stable_sort(customer, customer+ N, compare);
    
    for(int i = 0; i < N; i++){
        cout<<customer[i].first<<" "<<customer[i].second<<"\n";
    }
    return 0;
}

짝을 만드는 pair함수를 사용하여 int와 string을 짝으로 customer라는 변수를 배열로 선언하였다.

첫번째 for문은 단순히 값을 읽는 것이고 두번째 for문은 단순히 출력하는 것이다.

 

중요한건 중간의 stable_sort 이다.

아마 많이들 stable_sort를 sort로 서서 틀렸을 것이다.

stabled의 정의는 안정적인 이라는 뜻이다.

 

여기서 안정적이다 아니다 라는것 비교한 값이 같을때 순서의 변동이 있는지 없는지이다.

 

즉, stable_sort는 만약 비교한 값이 서로 같다면 입력한 순서를 그대로 유지한다는 것이다.

그게 안정적이니까

 

그럼 그냥 sort는?

sort는 불안정적인 sort로 비교한 값이 같을때 두번째 값들을 비교하여 기본적으로 오름차순정렬한다.

 

나는 처음 sort를 쓰기 위해 위에 compare이라는 함수까지 정의해서 했는데 틀리게 되었고 게시판에 반례를 둘러보던 중

stable_sort라는 것을 발견하게 되어 고쳐보니 맞았다.

 

아무래도 문제 정의상 안정적인것이 중요했기에 그냥 sort가 틀린 것이라고 생각한다.

 

결론 : 저거 사용자 함수 안썻어도 됬을거 같다..

 

전체 코드

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

bool compare(const pair<int, string> &cus1, const pair<int, string> &cus2){
    if(cus1.first == cus2.first){
        return false;
    }
    return cus1.first < cus2.first;
}
int main()
{
    int N;
    cin >> N;
    pair<int, string> customer [N];
    
    for(int i = 0; i < N; i++){
        cin>>customer[i].first>>customer[i].second;
    }
    
    stable_sort(customer, customer+ N, compare);
    
    for(int i = 0; i < N; i++){
        cout<<customer[i].first<<" "<<customer[i].second<<"\n";
    }
    return 0;
}

(해당 글은 제가 정보를 찾아보면서 이해한대로 작성했기에 틀렸을 수 있습니다.)