백준 C++ 10814번 나이순 정렬 ( stable_sort )

 

안녕하세요..! 

무거운 소식을 가지고 왔습니다.

 

4월 28일자로

BOJ 서비스가 종료된다고 합니다.

 

벌써 백준사이트를 들어가니

.. 서버를 반쯤 닫으셨는지

아니면 사람이 많이 들어와서 그런건지

엄청 서버가 느리다고 해야할까요..? 그랬습니다.

 

이제 새싹 문제를 끝냈는데..

이럴수가...

골드까지 함께해야죠..!!!!!

 

문제들이 남을지 안남을지 몰라서..

일단 class 2 단계를 오늘 내일까지만 풀고

마무리 지으려고합니다.

딱 문제도 4개 남았어요..!

 

너무 아쉽지만..네 오늘 이 문제를 풀어보겠습니다.

 

---

 

 

먼저 가입한사람이 뭘까..?

그럼 그냥 입력순이라는거겠지?

 

저번에 이와 비슷한 문제를 풀었었다.

 

2026.03.30 - [C++을 시작해봐요!/단계문제를 풀어보아요!] - 백준 C++ 1181번 단어 정렬 ( set, sort, pair )

백준 C++ 1181번 단어 정렬 ( set, sort, pair )

 

이 문제를 풀때,

set pair로 풀거나

 

sort로 풀었는데,

sort로 풀땐 함수를 하나 만들어서

숫자가 더 큰 애를 만들어 주었는데

 

이 문제는 비슷한듯 약간 다르다.

 

왜냐면 입력에 이미 들어온 순서대로 되어있고

이것을 고칠수 없기 때문..

그니까 굳이 뒤를 건들 필요가 없는것.

 

앞에 숫자만 조절하면 된다.

 

이럴경우 그냥 pair써서 첫번째만 sort 해주면 되지않을까? 라고 생각했다.

 

 

결국 엉켜버린..문법..

 

 

...긁적..

아니!!!!

cin을 안해줬잖아!!

 

 

 

좋아..

근데 이제 정렬하려니까 또 문제가 생긴다.

 

 

뭐지..

 

뭔가 안되나보다.

 

인지씨를 찾아갔다.

 

이런문법은 없단다..

ㅋ

 

그냥 sort해버리면,

첫번째값 정렬하고

첫번째값 같으면 두번째값도 사전순으로 정렬한다고 한다.

 

그럼 안된다!!

 

그래서 새로운 sort함수

stable_sort 함수를 써야한다고 알려주었다.

 

stable_sort? 처음듣는데..

 

stable_sort

 

sort는 순서를 보장해주지않고 오롯히 정렬만 하는데

stable_sort는 중복일때, 순서를 보장해준다고 한다.

 

하지만 여기서 이것만 달랑 쓰면 또 곤란하다.

 

왜냐

결국 이친구도 sort여서 

결국은 21이 같다고 판단해도

 

그 뒤에 글자가 다르기때문에

중복이라고 생각 안한다고 한다.

 

그래서 결국은 저번처럼 새로운 함수를 만들어야한다고 한다.

 

bool값으로 만들고

이번에는 pair로 만들었으니 pair로 입력값을 넣어줘야한다.

 

---

 

이친구의 역할은

a < b가 맞는지, 아닌지를 판별한다.

 

2랑 8이라고 해보자

 

 stable_sort(2, 8, Compare);

 

compare가 있네?

 

 

compare(2,8) 은 뭐죠?

 

2 < 8 을 return 하면 true 일것

8 < 2 면 false가 나오겠죠?

 

true요!

그러면 나는 이렇게 냅둬

 

반대로

8,2 였다고 해보자

 

false군요!

그럼 8이 앞이면 안되니까 2랑 바꿔!

그래서 결과는 2,8이 된다.

 

만약에 3,3 이면?

false죠? 왜냐면 < 니까

 

그러면 true가 아니니까 바꿔줘야하는데

나는 stable_sort니까 굳이 순서를 바꿔줄 필요가 없지

 

---

간단하게

 

순서가 맞을때

 

a < b ?

true

 b < a?

물어볼 필요도 없음

=> 아 이건 a가 무조건 작네 오케이

 

순서가 틀릴때

 

a < b ?

false

 b < a?

true

=> a가 더 작다는데? 무조건 바꿔!

 

값이 같을때

 

a < b ?

false

 b < a?

false

=> 서로 아니라는데? 그럼 같은가보다. 냅둬!

---

 

 

그래서 답은?!

 

이렇게 풀 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

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

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<pair<int, string>> v;

    for (int i = 0; i < n; i++)
    {
        int a;
        string b;
        cin >> a >> b;
        v.push_back({a, b});
    }

    stable_sort(v.begin(), v.end(), Compare);

    for (int i = 0; i < n; i++)
    {
        cout << v[i].first << " " << v[i].second << "\n";
    }
}

 

 

---

 

이 문제는

저번에 풀었던거라 그런지 조금은? 쉽게 풀 수 있었다.

bool compare 입력값이 조금 힘들었지만..말이다.

 

생각보다 간단할 줄 알았지만,

stable_sort도 그렇고..

 

v[i].first도 알고는 있었지만 아직은? 익숙치않았다.

 

그래도 풀었으니 됐다.

 

오래오래 기억하길

 

흑흑..

 

서비스가 종료되는게 실감이 드는중..

7분째 결과를 기다리고 있어요..

한시간째 안된다는 사람도 있긴한데..

아마 6시간 뒤에는 되지 않을까 싶어요..!

일단 네..

 

흑흑..얼른얼른 풀어야겠네요..!