BOJ 10814: 나이순 정렬

✔ 문제 링크

BOJ 10814: 나이순 정렬

---

✔ 문제해결전략

• Stable Sort or 구현

---

✔ 해결과정

나이순, 나이가 같으면 가입한 순으로 정렬을 하여야 한다. 나이가 같은 경우가 존재하므로 아무 sorting이나 사용해서는 안 된다. std::sort의 경우 quick sort로 구현되어 있는데 quick sort는 항상 같은 결과가 나오는 것이 보장되지 않는 unstable sorting이다. 따라서 sorting을 사용할 거면 stable sorting인 bubble, insertion, merge sort 등을 사용하면 된다. 1 ≤ N ≤ 100,000이고 시간제한이 3초이므로 O(N^2) sorting 알고리즘으로도 충분히 통과한다.

그런데 아무 생각 없이 std::stable_sort 사용하면 안 된다. pair<int,string>를 element로 갖는 vector를 사용하였는데 그러면 나이순으로 정렬하고 같은 나이에서는 입력순이 아닌 이름순으로 정렬하게 된다. 따라서 compare 함수를 조금 수정해야 한다.

Sorting을 하지 않는다면 1<=age<=200이므로 크기 201짜리 vector 잡은 다음에 입력받은 순서대로 나이에 맞는 칸에 삽입하면 된다. 그러면 같은 나이일 때 입력한 순서대로 삽입된다.

---

✔ 정답 CODE(std::stable_sort)

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

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<pair<int,string> > vec;

    int n;
    cin >> n;
    while(n--) {
        pair<int, string> info;
        cin >> info.first >> info.second;
        vec.push_back(info);
    }

    stable_sort(vec.begin(), vec.end(), compare);
    
    for(auto elem:vec) {
        cout << elem.first << " " << elem.second << '\n';
    }
    
}

---

✔ 정답 CODE(with vector)

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<vector<pair<int,string> > > vec(201);

    int n;
    cin >> n;
    while(n--) {
        pair<int, string> info;
        cin >> info.first >> info.second;
        vec[info.first].push_back(info);
    }
    
    for(int i=0;i<201;i++) {
        for(auto elem: vec[i]) {
            cout << elem.first << " " << elem.second << '\n';
        }
    }
    
}

---

✔ Stable Sort vs Unstable Sort

• 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되는지
• stable sort: Insertion Sort, Merge Sort, Bubble Sort, Counting Sort
• unstable sort : Heap Sort, Selection sort, Shell sort, Quick Sort

---

✔ Check Point

그동안 std::sort 3번째 parameter 신경 쓰지 않고 아무 생각 없이 사용해왔는데 이 문제 풀면서 3번째 parameter인 compare 함수 관련 내용을 다시 정리했다. default 오름차순 정렬이고, compare 함수를 넘겨줄 경우 참인 경우에 한해서 정렬을 한다.

---

✔ 참고자료

Stable Sort and Unstable Sort