백준 10814번 - 나이순 정렬 문제 C++ sort()/stable_sort()

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

 

---

🧩 문제 요약

나이와 이름이 입력될 때 나이순으로 정렬하여 출력하라.

단, 나이가 같은 경우 입력 순으로 출력. 

 

---

👍 이 문제에서 배운 점 

 

이 문제에서 아주 중요한 부분은 나이가 같은 경우 입력순으로  처리하라는 것이다. 

이말은 stable하게 정렬하라는 말과 동일하다. 

 

처음에는 sort()를 사용해도 여러 테스트 케이스에서 stable하게 출력이 되길래 별로 문제가 없다고 생각했는데,

백준 히든 케이스에서 자꾸 통과하지 못했다. 

 

그래서 찾아보니 sort()는 stable하지 못하다.

 

✅ stable이란? 

👉 stable: 동일한 값들의 순서를 보장.

일반적인 정렬 알고리즘은 동일한 값들의 순서를 보장하지 않는다. 그래서 정렬 후의 순서가 원래 순서와 다를 수 있다. 

 

예를 들어, 똑같이 5가 두번 입력되었을 때 [5, 5] 

• 먼저들어온 5를 5_a
• 나중에 들어온 5를 5_b

라고 한다면, 

정렬 이후에도 5_a, 5_b의 순서를 유지하는지 아니면 5_b, 5_a로 순서를 유지 하지 못하는 지를 판단하는 것이다. 

전자와 같은 경우를 stable하다고 하고 후자와 같은 경우를 stable하지 않다고 한다. 

 

 

그럼 stable하게 sort를 하고 싶으면 어떻게 해야할까? 

stable_sort를 사용하면 된다. 

 

✅ stable_sort()

stable_sort는 sort와 사용방법은 동일하다. 

다만, 정렬 후 결과가 stable한 것을 보장해준다.

sort()와 stable_sort() 둘다 시간 복잡도는 O(nlogn) 으로, 대략적으로 nlogn번의 비교를 수행한다.

 

하지만, stable_sort()는 동일한 값들 사이의 상대적인 순서를 유지하는 추가적인 작업이 필요하기 때문에, 실제 실행 시간은 sort()보다 약간 더 길 수 있다. 

 

 

✅ pair 클래스 

이 문제에서는 age와 name 자료형이 다른 값을 입력을 받게된다. 

이렇게 변수 타입은 다르지만 연관된 데이터를 관리할 때는 pair를 사용하면 편리하다. 

👉 pair를 사용해서 2개 타입의 데이터를 저장할 수 있다. 

 

C++에서 pair는 <utility> 헤더파일에 존재하는 STL이다. 

<utility> 헤더파일은 <algorithm>과 <vector>에 포함되어 있기 때문에 굳이 따로 include할 필요는 없다. 

 

✔. pair 클래스의 형태는 다음과 같다. 

template <class T1, class T2> struct pair;

 

✔. 함수의 사용법 

// pair class의 객체 생성
pair<int, int> p
pair<int, string> p
pari<double, char> p
...

• p.first : p의 첫번째 인자를 반환.
• p.second : p의 두번쨰 인자를 반환.
• make_pair(값1, 값2) : 값1, 값2를 한 쌍으로 하는 pair를 만들어서 반환. 

 

---

🧾내가 작성한 코드 

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

using namespace std; 

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

int main(){
   int n, i, age ; 
   string name; 
   vector<pair<int, string>> crews;
   cin >> n ; 

   for(i=0; i<n ; i++){
       cin >> age >> name ; 
       crews.push_back(make_pair(age, name));
   }
   stable_sort(crews.begin(), crews.end(), compare);

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

---