백준 2910번 : 빈도 정렬 (C++)

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

2910번: 빈도 정렬

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
int main() {
    int N, C;
    std::cin >> N >> C;
 
    std::map<int, int> frequencyMap;
    std::map<int, int> orderMap;
    int number;
 
    for (int i = 0; i < N; i++) {
        std::cin >> number;
        frequencyMap[number]++;
 
        if (orderMap[number] == 0)
            orderMap[number] = i + 1;
    }
 
    std::vector<std::pair<int, int>> frequencyList(frequencyMap.begin(), frequencyMap.end());
 
    std::sort(frequencyList.begin(), frequencyList.end(), [&](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        if (a.second == b.second)
        return orderMap[a.first] < orderMap[b.first]; // 기존의 순서 지키기
 
    return a.second > b.second;
        });
 
    for (const auto& freq : frequencyList) {
        for (int i = 0; i < freq.second; i++) {
            std::cout << freq.first << " ";
        }
    }
 
    return 0;
}

C언어로 문제를 해결하고자 하였지만 계속해서 메모리초과가 발생하여 C++로 풀게 되었다..

문제 설명

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했습니다. 그 방법은 빈도를 조사하는 것입니다. 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했습니다. 이 메시지는 숫자 N개로 이루어진 수열이며, 숫자는 모두 C보다 작거나 같습니다. 창영이는 이 숫자를 자주 등장하는 빈도 순대로 정렬하려고 합니다. 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 합니다. 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 합니다. 이렇게 정렬하는 방법을 빈도 정렬이라고 합니다.

코드 설명

 

1. 입력으로 메시지의 길이 N과 C를 받습니다.
2. 메시지 수열을 입력받고, 빈도수를 계산하며, 먼저 등장한 수의 순서를 저장합니다.
3. 빈도수를 기준으로 pair로 변환하여 vector에 저장합니다.
4. 정렬을 수행합니다. 빈도수가 같을 경우, 먼저 등장한 수의 순서를 기준으로 정렬합니다.
5. 정렬된 결과를 출력합니다.