[BOJ] 10814 나이순정렬, Stable의 뜻

1. 문제링크

https://www.acmicpc.net/problem/10814

2. 문제해설

이 문제는 n명의 사람이 주어지는데, 이 사람들을 먼저 나이순으로, 그리고 먼저 들어온 순으로 정렬 하는 문제이다.

이 문제는 여러가지 방법으로 풀 수 있다.

vector를 사용해 입력 순서대로 정리

1. string을 받는 vector 배열에 나이에 해당하는 인덱스에 push_back을 해준다.

2. 배열을 돌면서 출력해준다.

ps) vector말고 FIFO인 자료구조이면 뭐든 괜찮다. 핵심은 먼저 들어간 것이 먼저 나오는 데에 있다.

이 풀이의 시간복잡도는 O(N) 이다.

count_sort를 이용한 풀이

1. 입력받은 사람들의 나이를 cnt배열에 카운팅한다.

2. cnt 배열의 누적합을 구한다.

3. 각 배열의 누적합의 시작점이 뜻하는 바는, 그 숫자들의 마지막 index 라는 점이다.

4. 이를 이용해서 뒤에서부터 확인하면서 배열의 index를 찾아서 ans배열에 집어넣는다.

5. 출력한다.

이 풀이의 시간복잡도는 O(max(age)) 이다.

stable_sort를 이용한 풀이

1. standard_libarary에 stable_sort라는 또 다른 sort가 있다. 이를 이용한다.

ps) stable_sort는 algorithm 헤더파일에 있다.

이 풀이의 시간복잡도는 O(NlogN) 이다.

3. 소스코드

1. vector를 사용한 풀이

#include<iostream>
#include<vector>
#include<string>
#define MAXNUM 100010
#define fio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;

int main(){
    fio;
    int n;
    vector<string> v[201];
    cin >> n;
    for (int i=0; i<n; i++) {
        int x; string name;
        cin >> x >> name;
        v[x].push_back(name);
    }
    
    for (int i=0; i<201; i++) {
        for (int j=0; j<v[i].size(); j++) {
            cout << i << ' ' << v[i][j] << '\n';
        }
    }
    
    return 0;
}

2. count_sort를 이용한 풀이

#include<iostream>
#include<string>
#define MAXNUM 100010
#define fio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;

struct user{
    int age;
    string name;
};

int main(){
    fio;
    int n;
    int age[201]={0};
    int sum[201]={0};
    user arr[MAXNUM];
    user ans[MAXNUM];
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> arr[i].age >> arr[i].name;
        age[arr[i].age]++;
    }
    
    for (int i=1; i<201; i++) {
        sum[i] = sum[i-1] + age[i];
    }
    
    for (int i=n-1; i>=0; i--) {
        ans[--sum[arr[i].age]] = arr[i];
    }
    
    for (int i=0; i<n; i++) {
        cout << ans[i].age << ' ' << ans[i].name << '\n';
    }
    
    return 0;
}

3. stable_sort를 이용한 풀이

#include<iostream>
#include<algorithm>
#include<string>
#define MAXNUM 100010
#define fio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;

struct user{
    int age;
    string name;
    bool operator < (const user & a) const{
        return age < a.age;
    }
};

int main(){
    fio;
    int n;
    user arr[MAXNUM];
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> arr[i].age >> arr[i].name;
    }
    
    stable_sort(arr, arr+n);
    
    for (int i=0; i<n; i++) {
        cout << arr[i].age << ' ' << arr[i].name << '\n';
    }
    
    return 0;
}

4. 추가 언급

세번째 풀이를 보면 특이한 점이 있다. sort를 사용하지 않고 stable_sort라는 다른 이름의 sort를 사용한 것이다. 일반적으로 우리는 sort를 한다고 하면 algorithm 헤더파일에 있는 sort함수를 사용한다. 그러면 stable_sort와 sort의 차이점은 무엇일까?

결론만 말하자면 sort는 stable하지 않고, stable_sort는 stable하다. 그렇다면 stable이라는 특징은 도데체 무엇일까?  

stable한 특징은 위의 문제가 가진 조건과 동일하다. sort를 끝냈을 때, 같은 수라면 앞에 있는 애들이 sort가 끝난 배열에서도 앞에 있어야 한다는 것이다. 아래의 그림을 보면 더 이해가 잘 될 것이다.

(출처 : https://en.wikipedia.org/wiki/Sorting_algorithm#Stability)

이렇게 같은 수 (5 heart와 5 spade)는 앞에 있는 5 heart가 앞에 오고 5 spade가 뒤에 오는 것이 stable한 sort인 것이다. 이러한 특징을 가진 내장 sort 함수는 stable_sort이다.

그렇다면 sort함수는 무슨 소트 알고리즘을 쓴 것이고, stable_sort는 무슨 알고리즘을 사용한 것일까?

sort는 기본이 되는 소트가 quick_sort이다. 물론 크기에 따라 나누고, 최악의 케이스일 때는 다르게 소트하는 등 추가 기법들이 들어가 있지만 어찌 됐든 quick_sort를 기본으로 하는 sort이다. 그래서 quick_sort는 stable한 sort가 아니기 때문에 stable_sort가 되지 못하는 것이다.

stable_sort는 기본이 merge_sort로 되어 있다. merge_sort는 nlogn을 보장해주지만 quick_sort에 비해서 메모리와 시간을 더 잡아먹는다. 그렇기에 우리는 일반적으로 sort를 쓰고 특별한 경우에만 stable_sort를 사용하는 것이다.

위의 예제에도 있겠지만 stable하게 counting sort를 하는 방법도 만들어 낼 수 있다. 물론 일반 counting sort보다는 더 많은 시간이 소요 되지만, big O notation으로는 같은 O(n + k)의 시간 복잡도가 들어가기 때문에 필요하다면 stable_sort보다는 counting sort로 푸는 것이 더 빠를 수도 있다.

실제로 메모리와 시간을 비교해보면 

counting sort

vector

stable_sort

이렇게 된다.