알고리즘/BOJ

백준 2910번 빈도 정렬

꾸준함. 2024. 3. 13. 07:13

문제 링크입니다: https://www.acmicpc.net/problem/2910

 

2910번: 빈도 정렬

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

www.acmicpc.net

 

map의 특성을 이용하여 visited 배열과 같이 사용하면 메모리 초과가 발생하지 않고 쉽게 풀 수 있는 문제였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef struct
{
int num;
int initIdx;
int cnt;
} State;
bool cmp(State& a, State& b)
{
if (a.cnt > b.cnt)
{
return true;
}
if (a.cnt == b.cnt)
{
if (a.initIdx < b.initIdx)
{
return true;
}
}
return false;
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, C;
cin >> N >> C;
map<int, int> num2idx;
vector<State> v;
int idx = 0;
for (int i = 0; i < N; i++)
{
int num;
cin >> num;
if (!num2idx.count(num))
{
v.push_back({ num, idx, 1 });
num2idx[num] = idx++;
}
else
{
v[num2idx[num]].cnt++;
}
}
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < v.size(); i++)
{
for (int j = 0; j < v[i].cnt; j++)
{
cout << v[i].num;
if (!(i == v.size() - 1 && j == v[i].cnt - 1))
{
cout << " ";
}
}
}
cout << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형