[백준 c++] 2910 빈도 정렬

문제 설명

https://www.acmicpc.net/problem/2910
숫자 N개로 이루어진 수열이 모두 C보다 작거나 같을 때 수열을 빈도 정렬 하는 문제다.

아이디어

커스텀 정렬을 이용하여 푸는 문제

1차 시도

1. vector<pair<int,int>>를 사용해서 first에 입력된 숫자, second에 입력된 횟수 저장
2. compare함수로 second값이 크면 앞으로 오게 순서 바꿈

이런저런 예제를 넣었을 때 잘 돌아간다고 생각해서 제출해봤더니 틀렸다.

2차 시도

등장한 횟수가 같으면 먼저 나온 수를 우선으로 출력한다는 조건도 처리해줘야 했다.

그런데 기존 vector만 가지고 비교해도 먼저 온 것이 먼저 나오는 조건을 만족시키는거 아닌가 하는 의문이 들었다.
https://www.acmicpc.net/board/view/91806
백준 질문에 나랑 똑같은 질문이 있었다.
이 질문의 답변에 의하면 sort 함수의 최종 정렬 결과에서 조건에 해당하는 순서가 유지되는 것이 보장되지 않는다고 한다.
추가로 두 원소가 같은 경우 기존의 순서를 유지해주는 정렬은 stable_sort로 구현할 수 있다고 한다.

그래서 기존의 코드에서 sort를 stable_sort로 바꿨더니 정답처리 됐다.

---

전체 코드

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;
int n, c;
vector<pair<int, int>> a;
bool compare(pair<int, int> a, pair<int, int> b)
{
    return a.second > b.second;
}
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 k;
        cin >> k;
        //아 애초에 a.size가 0이구나...
        if (a.size() == 0)
        {
            a.push_back(make_pair(k, 1));
            continue;
        }
        for (int j = 0; j < a.size(); j++)
        {
            if (a[j].first == k)
            {

                a[j].second++;
                break;
            }
            if (j == a.size() - 1)
            {
                a.push_back(make_pair(k, 0));
            }
        }
    }
    
    stable_sort(a.begin(), a.end(), compare);
    
    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < a[i].second; j++)
        {
            cout << a[i].first << " ";
        }
    }
}