[BOJ/2910/C++] 빈도 정렬

출처:https://www.acmicpc.net/problem/2910

문제

• 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

• 만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

• 수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

조건

• 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)
• 둘째 줄에 메시지 수열이 주어진다.

풀이

만약, C의 범위가 작았다면, 직접 세는 방법을 이용할 수도 있겠지만 숫자범위가 10억이므로, 위 정렬방법에는 Map 자료구조가 적합해보인다.

Map은 key ,value쌍으로 이루어져있고, Map[Key]로 접근이 가능하다.

각각의 입력을 key로 value는 해당 숫자의 갯수를 세어주고, order Map에는 각 숫자가 처음 등장한 순서를 입력해준다.

정렬을 할 때, 위의 조건대로 빈도 수를 우선시하고, 그 뒤에 빈도수가 같다면 등장한 순서를 기반으로 정렬을 해주는 Compare 함수를 만들어주면 된다!

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N, C;
map<int, int> order;

bool comp(pair<int, int> &a, pair<int, int> &b)
{
  // 만약, 두 숫자의 빈도수가 같다면, 먼저 나온 친구가 앞에.
  if (a.second == b.second)
  {
    return order[a.first] < order[b.first];
  }
  return a.second > b.second;
}

int main()
{
  fastio;
  map<int, int> freq;
  cin >> N >> C;

  int tmp;
  for (int i = 0; i < N; i++)
  {
    cin >> tmp;
    freq[tmp]++;
    // 원소들의 나온 순서를 저장하는 map
    if (order[tmp] == 0)
      order[tmp] = i + 1;
  }
  vector<pair<int, int>> vec(freq.begin(), freq.end());

  sort(vec.begin(), vec.end(), comp);
  for (auto v : vec)
  {
    for (int i = 0; i < v.second; i++)
    {
      cout << v.first << " ";
    }
  }
  return 0;
}