문제 링크입니다: https://www.acmicpc.net/problem/2910
2910번: 빈도 정렬
첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다.
www.acmicpc.net
map의 특성을 이용하여 visited 배열과 같이 사용하면 메모리 초과가 발생하지 않고 쉽게 풀 수 있는 문제였습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |

개발환경:Visual Studio 2022
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
백준 17298번 오큰수 (0) | 2024.03.15 |
---|---|
백준 2870번 수학숙제 (1) | 2024.03.13 |
백준 4659번 비밀번호 발음하기 (0) | 2024.03.13 |
백준 25596번 마트료시카 박스 II (0) | 2022.09.22 |
백준 25516번 거리가 K이하인 트리 노드에서 사과 수확하기 (0) | 2022.09.04 |