[알고리즘] 2910번: 빈도 정렬

0. 문제

 

2910번: 빈도 정렬

 

---

1. 문제 이해

 

1. 정렬에는 두 가지 정보가 필요함.
2. 숫자의 빈도
   1. c++의 int는 4바이트로 –2,147,483,648 ~ 2,147,483,647 값을 가진다.
   2. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)
3. 숫자의 등장 순서
   1. “숫자”에서 “등장 순서”를 얻을 수 있어야 함.
4. vector와 map 두 개를 사용하기.
5. 또는 vector에 tuple을 넣고 커스텀 함수로 정렬하기.
   1. tuple<int, int, int> 생성하고 정렬하기. → 빈도는 내림차순, 순서는 오름차순 정렬임. → 커스텀 정렬 함수를 사용해야 함.

 

---

2. 제출

 

가. 컴파일 에러 (Segfault)

// 백준 2910번: 빈도 정렬
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>

using namespace std;

int n, c;
map<int, int> cnt, seq;
vector<int> v;

bool cmp(int a, int b){
    if(cnt[a] == cnt[b]) return seq[a] <= seq[b];
    return cnt[a] > cnt[b];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> c;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
        cnt[tmp]++;
        if(cnt[tmp] == 1) seq[tmp] = i;
    }
    sort(v.begin(), v.end(), cmp);

    for(int item : v){
        cout << item << " ";
    }

    return 0;
}

bool cmp(int a, int b){
    if(cnt[a] == cnt[b]) return seq[a] <= seq[b];
    return cnt[a] > cnt[b];
}

cmp 함수에서 seq를 사용할 때, 같은 빈도수를 가진 값들 사이의 순서를 올바르게 유지하기 위해 seq[a] <= seq[b]로 설정했다.

 

하지만 이러한 방식은 “stable”한 정렬 알고리즘에만 유용합니다.

 

stable이란 정렬 알고리즘의 특성 중 하나로, 같은 값의 원소들 사이의 상대적인 순서가 정렬 전과 정렬 후에 동일하게 유지되는 특성을 의미한다.

 

그러나 std::sort는 기본적으로 stable한 정렬을 보장하지 않는다.

 

만약 stable한 정렬이 필요한 경우에는 std::stable_sort를 사용해야 한다.

 

---

나. 수정

 

• stable_sort 사용

// 백준 2910번: 빈도 정렬
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>

using namespace std;

int n, c;
map<int, int> cnt, seq;
vector<int> v;

bool cmp(int a, int b){
    if(cnt[a] == cnt[b]) return seq[a] < seq[b];
    return cnt[a] > cnt[b];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> c;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp); // 수정
        cnt[tmp]++;
        if(cnt[tmp] == 1) seq[tmp] = i; // 수정
    }

    stable_sort(v.begin(), v.end(), cmp); // sort 대신 stable_sort 사용

    for(int item : v){
        cout << item << " ";
    }

    return 0;
}

 

• sort 사용

// 백준 2910번: 빈도 정렬
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>

using namespace std;

int n, c;
map<int, int> cnt, seq;
vector<int> v;

bool cmp(int a, int b){
    if(cnt[a] == cnt[b]) return seq[a] < seq[b]; // 수정
    return cnt[a] > cnt[b];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> c;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        cnt[tmp]++;
        if(cnt[tmp] == 1){
            seq[tmp] = i;
            v.push_back(tmp); // 이동
        }
    }
    sort(v.begin(), v.end(), cmp);

    for(int item : v){
        for(int i=0; i<cnt[item]; i++)  // 추가
            cout << item << " ";
    }

    return 0;
}

 

---