[백준/C++] 10814번: 나이순 정렬 - Stable Sort

1. 문제 정보

• 문제 번호: 10814번
• 문제 이름: 나이순 정렬
• 문제 요약: 온라인 저지 회원들의 나이와 이름이 가입 순서대로 주어진다. 회원들을 나이가 증가하는 순으로 정렬하되, 나이가 같으면 먼저 가입한(입력된) 순서를 유지하여 출력해야 한다.

 

2. 접근 방법 (알고리즘)

처음 문제를 봤을 때 '나이'와 '이름'이 한 쌍으로 움직여야 한다고 생각했다.

❌ 첫 번째 접근: Map 사용

데이터가 (Key, Value) 형태 같아서 std::map<string, int> 혹은 map<int, string>을 떠올렸다. 하지만 Map은 적절하지 않았다.

1. 자동 정렬: Map은 Key를 기준으로 자동 정렬된다. 문제의 조건(나이 순 → 가입 순)을 맞추기 까다롭다.
2. 중복 문제: 나이가 같은 사람이 여러 명이거나, 이름이 같은 사람이 있을 수 있는데 Map은 Key 중복을 허용하지 않는다.

❌ 두 번째 접근: Vector + Sort (불안정 정렬)

vector<pair<int, string>>을 사용하여 데이터를 저장하고 sort 함수를 돌렸다. 하지만 일반적인 sort는 불안정 정렬(Unstable Sort)이다. 나이가 같을 때, 입력된 순서가 유지된다는 보장이 없다.

✅ 최종 접근: Vector + Stable Sort

입력 순서(가입 순서)를 유지해야 한다는 조건("나이가 같으면 먼저 가입한 사람이 앞에 온다")을 만족하기 위해 stable_sort (안정 정렬)를 사용하기로 결정했다.

 

3. 코드 구현 (정답)

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

int main() {
    int n;
    cin >> n;
    
    // 나이(int)와 이름(string)을 묶어서 저장할 벡터 생성
    vector<pair<int, string>> m;
    
    for(int i=0; i<n; i++){
        int age;
        string name;
        cin >> age >> name;
        
        // pair로 묶어서 벡터에 추가
        m.push_back({age, name});
    }

    // stable_sort: 값이 같을 때 기존 순서(입력 순서)를 보장함
    stable_sort(m.begin(), m.end(), [](const pair<int,string> &a, const pair<int,string> &b){
        return a.first < b.first; // 오직 나이(first)만 비교 (나이가 같으면 입력 순 유지됨)
    });

    // 출력
    for(auto &p : m){
        cout << p.first << " " << p.second << "\n";
    }

    return 0;
}

---

 

4. 배운 점 & 회고 (TIL) ✍️

이번 문제를 풀면서 자료구조의 특성과 정렬 함수의 차이를 명확히 알게 되었다.

① std::map의 특징과 한계

처음엔 map을 쓰려다 실패했다.

• 자동 정렬: map은 내부적으로 Red-Black Tree를 사용하여 Key를 기준으로 오름차순 정렬된다. 내가 원하는 기준(Value 등)이나 입력 순서를 유지하기 어렵다.
• 중복 불가: 동일한 Key가 들어오면 기존 값을 덮어쓰거나 무시한다. (중복을 허용하려면 multimap을 써야 함)

map 개념 참고 

② std::pair의 활용

• 두 개의 데이터를 하나로 묶어 관리할 때 pair가 아주 유용하다.
• first와 second로 접근하며, vector와 함께 사용하여 Struct처럼 활용할 수 있다. 

• vector<pair<int, string>> v;
  v.push_back({20, "Kim"});
  

• pair 개념 참고

 

③ Sort vs Stable Sort (안정 정렬의 중요성)

이 문제의 핵심은 "나이가 같으면 가입한 순서를 유지하라"는 조건이었다.

• sort (Unstable Sort): 퀵 소트(Quick Sort) 기반. 빠르지만($O(N \log N)$), 비교하는 값이 같을 때 원래의 순서가 뒤바뀔 수 있다.
• stable_sort (Stable Sort): 머지 소트(Merge Sort) 기반. 값이 같으면 입력된 순서(기존 순서)를 그대로 유지한다.
• 결론: 정렬 조건에 "원래 순서 유지"라는 말이 있다면 무조건 stable_sort를 사용해야 한다.

stable_sort()와 sort 차이 알아보기 

 

++추가로 sort의 comparator 의 true false 의미를 알게되었다. 

📌 정리

• sort의 comparator는 "앞에 와야 하면 true"라는 규칙을 따릅니다.
• ageA < ageB는 "나이가 더 작은 쪽을 앞으로 보내라"는 의미가 됩니다.
• 결과적으로 나이 오름차순 정렬